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

PreviousRemoving Duplicates from a List NextConcatenating Two Lists

Last updated 5 years ago

Was this helpful?

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; } }

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; }

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)