Reversing a Linked List

Iterative and recursive approaches to reverse a linked list.

Reversing by Changing Node Data & Using an Array :

• Pass the pointer to head node and an array as parameters.

• Using a while loop, copy the data from each node to the array until the pointer becomes NULL.

• Set the pointer to head and decrement to index i by 1 to reach the last element of array.

• Overwrite the data in each node using a while loop and keep decrementing the index i until pointer becomes NULL.

void reverse(struct node *ptr, int a[]) {
    
    // A variable to keep track of array index
    int i = 0;
    
    // Copy data from linked list to array
    while (ptr != NULL) {
        a[i] = ptr -> data;
        i++;
        ptr = ptr -> next;
    }
    
    // Set index to begin reverse procedure
    ptr = head;
    i--;
    
    // Copy data from array to linked list in reverse
    while (ptr != NULL) {
        ptr -> data = a[i];
        i--;
        ptr = ptr -> next;
    }
    
}

Reversing using Sliding Pointers :

• Take two additional pointers, prev and next, and initialise them with NULL.

• Copy the next address of each node to the next pointer and then set the next address of node to the prev pointer.

• Make current as next and prev as current in order to move forward.

• Do this procedure until current becomes NULL.

• Set the head node as prev pointer.

void reverse(struct node *ptr) {

    // Consider ptr to the pointer to current node
    struct node *prev = NULL;
    struct node *next = NULL;

    while (ptr != NULL) {
        // Store the address of next node
        next = ptr -> next;
        // Make the next of each node point to its previous
        ptr -> next = prev;
        // Move forward
        prev = ptr;
        ptr = next;
    }
    // Setting the value of head node
    head = prev;   
}

Reversing by Recursion :

void reverse(struct node *prev, struct node *curr) {

    if (curr != NULL) {
        reverse(curr, curr -> next);
        curr -> next = prev;        
    } else {
        head = prev;
    }

}

// Function call : reverse(NULL, head) 

Contributed by Nitin Ranganath