Question

Describe in detail an algorithm for reversing a singly linked list L using only a constant amount of additional space and not using any recursion.

Answer 1

For reference, I would use the following node class.

class Node {

    int data;

Node next;

};

Step 1: We need to initialize three-pointers prev as NULL, curr as head and next as NULL.

Step 2: We will iterate the linked list and do the following :

Node reverse(Node node) {

        Node prev = null; //initialised prev to null

        Node current = node; // initialised current to node ,where node is the starting node of the linked list. we will use current to iterate in the linked list

        Node next = null; //initialised next to null.

        while (current != null) { //basically we are using three pointers to reverse the links in a linked list.

// prev -> current -> next will get converted to prev <- current <- next ...eventually current would become null

// and linked list would become a <- b <- ......<- prev i.e prev would become the new head and we will return prev

// node

            next = current.next;  

            current.next = prev;

            prev = current;

            current = next;

        }

        node = prev;

        return node;

    }

//Dry run the code on paper. if you still have any doubts, feel free to comment.