Technical Questions‎ > ‎DS‎ > ‎Linked List‎ > ‎

Solution

1. Reverse the Linked List.
    
    static void Reverse(struct node** headRef) {
    
    struct node* result = NULL;
    struct node* current = *headRef;
    struct node* next;
    
    while (current != NULL) {
        next = current->next; // tricky: note the next node
        current->next = result; // move the node onto the result
        result = current;
        current = next;
    }
    
    *headRef = result;
    }

2. Reverse the Linked List recursively.

    void RecursiveReverse(struct node** headRef) {
    
    struct node* first;
    struct node* rest;
    
    if (*headRef == NULL) return; // empty list base case

    first = *headRef; // suppose first = {1, 2, 3}
    rest = first->next; // rest = {2, 3}

    if (rest == NULL) return; // empty rest base case
    RecursiveReverse(&rest); // Recursively reverse the smaller {2, 3} case
                                        // after: rest = {3, 2}

    first->next->next = first; // put the first elem on the end of the list
    first->next = NULL; // (tricky step -- make a drawing)
    *headRef = rest; // fix the head pointer
    }
Comments