Introduction

Given a linked list of N nodes. The task is to reverse this list.

Input:
LinkedList: 1->2->3->4->5->6
Output: 6 5 4 3 2 1
Explanation: After reversing the list, 
elements are 6->5->4->3->2->1.
Example

Approach

The approach is to use iteration and three pointers, previous, current and next. We set the current pointer to head and continue iteration.

We reverse the current pointer next to previous during the traversal and update current with the next pointer.

   // Reverse sample using prev, curr and next
    
   Null    A -> B -> C
   Prev  Curr  Next
   
   NULL <- A    B -> C
         Prev  Curr  Next

   NULL <- A <- B    C
              Prev  Curr  Next

   NULL <- A <- B <- C
                    Prev  Curr  Next
Understanding the approach with the pointers in action
//function Template for Java

/* linked list node class:

class Node {
    int value;
    Node next;
    Node(int value) {
        this.value = value;
    }
}

*/

class ReverseLL
{
    // This function should reverse linked list and return
    // head of the modified linked list.
    Node reverseList(Node head)
    {
        if (head == null) {
            return null;
        }
        
        Node prev = null;
        var curr = head;
        // set first in the while loop
        Node next = null;
        while (curr != null) {
            next = curr.next;
            // curr next is stored in the next pointer
            curr.next = prev;
            // set the prev to curr
            prev = curr;
            curr = next;
        }
        return prev;
    }
}
Java program to reverse a linked list using previous, current and next pointer