March 20, 2012

Reverse a Singly Linked List - Recursive and Iterative

Question: Write a C program to reverse a singly linked list.

Find below both recursive and iterative functions to reverse a link list. Both functions have same time complexity. Recursive function is called as head = list_reverse1(head, NULL), it returns a pointer to the head of the new list. Iterative function call is self explanatory.

Time Complexity: O(n)

/* recursive */

list *list_reverse_recursive(list *curr, list *prev)
{
    list *head = NULL;

    if (curr == NULL) {
        return prev;
    }

    head = list_reverse_recursive(curr->next, curr);
    curr->next = prev;

    return head;
}

/* iterative */
void list_reverse_iterative(list **head)
{
    list *prev = NULL, *curr = *head, *next = NULL;

    while (curr != NULL) {
        next = curr->next;

        curr->next = prev;
        prev = curr;
        curr = next;
    }
    *head = prev;
}




2 comments: