Algorithm Patterns 101: Reversing Linked List

Linked List is a data structure which stores the data in a linear way. Unlike an array, data in a linked-list is non-contiguous (aka the data does not exist next to each other).

Each element of a linked list contains a data field to store the list data and a pointer filed to point to the next element in the sequence.

After we reverse the linked list, the head will point to the last element of the original linked list. The previous pointers will be reversed to the previous element.

Step-By-Step (In-Place Reversal)

To reverse the entire linked list without occupying extra memory, we can utilize the in-place reversal pattern.

• Initialize three pointers: prev, next, and curr. The prev and next pointers are initialized as NULL, while the curr pointer is initialized to the head of the linked list.

• Iterate over the linked list. While iterating, perform the following steps:
  • Before change the next of curr, store the next node using the following line of code next = curr.next

• Now, we will update the next pointer of curr with the prev pointer. This will reverse the pointer of the current node from forward to backward, eventually aiding the reversal of the linked list.

• After reversing the pointer, we’ll update prev as curr and curr as next using prev = curr and curr = next respectively.

• Update the next pointer to the next curr to store the next curr.

class Node {
   public int data;
   public Node next;

   public Node(int data) {
       this.data = data;
       this.next = null;
   }
}

class LinkedList {
    public Node head;

    public LinkedList() {
        this.head = null;
    }

    public Node reverse(Node head) {
        //We define a prev set to the previous node so we have somewhere to point. We must create it because it doesn't technically exist.
        Node prev = null;
        //Keeps track of the node we are currently on as we are traversing the linked list
        Node curr = head;
        
        while(curr != null) {
            //We need to save the next node in line because we will not have access once we change the pointer
            Node next = curr.next;
            //In this line we are setting the next pointer of the current node to the previous
            curr.next = prev;
            //Then we move along the linked list by setting the previous node to curr and the curr to the next
            prev = curr;
            curr = next;
        }

        head = prev;
        return head;
    }

    public void insert(Node node) {
        if(this.head == null) {
            this.head = node;
        } else {
            node.next = this.head;
            this.head = node;
        }
    }
}