Tuesday, October 9, 2012

Reverse a given Linked List

Write an Reverse() function which reverses a list by rearranging all the .next pointers and the head pointer.
 
/* 
 * Iteratively reverse the given linked list by changing its .next pointers and
 * its head pointer. Takes a pointer (reference) to the head pointer.
 */
void Reverse(nodeptr* headRef)
{
    nodeptr current = *headRef, nextNode, tempNode;
    if(current == NULL || current->next == NULL) return;
    else {
        nextNode = current->next;
        current->next = NULL;
        while(nextNode != NULL) {
            tempNode = nextNode->next;
            nextNode->next = current;
            current = nextNode;
            nextNode = tempNode;
        }
        *headRef = current;
    }
}

/*
 * Recursively reverses the given linked list by changing its .next
 * pointers and its head pointer. Takes a pointer (reference) to the
 * head pointer.
 */
void RecursiveReverse(nodeptr* headRef)
{
    nodeptr current, rest;
    if(current == NULL) return;
    current = *headRef;
    rest = current->next;
    if(rest == NULL) return;
    RecursiveReverse(&rest);
    current->next->next = current;
    current->next = NULL;
    *headRef = rest;
}

No comments:

Post a Comment