Course4all
Join us on telegram
Home/dsa/Linked List Patterns/Reverse Linked List

Reverse Linked List

Master this topic with zero to advance depth.

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

Visual Representation

List: 1 -> 2 -> 3 -> null Step 1: Current=1, Next=2. 1.next points to null. Step 2: Current=2, Next=3. 2.next points to 1. Step 3: Current=3, Next=null. 3.next points to 2. Result: 3 -> 2 -> 1 -> null
Easy

Examples

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Approach 1

Level I: Brute Force (Stack)

Intuition

Push all node values onto a stack. Since a stack is Last-In-First-Out (LIFO), popping them will give the values in reverse order. Then, create a new list with these values.

⏱ O(N)💾 O(N)

Detailed Dry Run

List: 1->2->3.

  1. Push 1, 2, 3 to stack.
  2. Pop 3: New list 3.
  3. Pop 2: 3->2.
  4. Pop 1: 3->2->1.
java
public ListNode reverseList(ListNode head) {
    Stack<Integer> stack = new Stack<>();
    while (head != null) {
        stack.push(head.val);
        head = head.next;
    }
    ListNode dummy = new ListNode(0), curr = dummy;
    while (!stack.isEmpty()) {
        curr.next = new ListNode(stack.pop());
        curr = curr.next;
    }
    return dummy.next;
}

⚠️ Common Pitfalls & Tips

O(N) space makes this less efficient than in-place methods.

Approach 2

Level II: Recursive

Intuition

Base case: if head is null or next node is null, return head. Recursive step: reverse the rest of the list, then point the next node's next back to head.

⏱ O(N)💾 O(N) recursion stack

Detailed Dry Run

1->2->3.

  1. reverseList(2->3).
  2. reverseList(3) returns 3.
  3. Back at 2: 2.next (3).next = 2. 2.next = null. List: 3->2->null.
  4. Back at 1: 1.next (2).next = 1. 1.next = null. List: 3->2->1->null.
java
public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

⚠️ Common Pitfalls & Tips

Easy to forget to set head.next = null, causing deep cycles.

Approach 3

Level III: Optimal (Iterative In-place)

Intuition

Use three pointers: prev, curr, and next. Iterate through the list, changing each node's next pointer to point to the prev node.

⏱ O(N)💾 O(1)

Detailed Dry Run

1->2->3. Prev=null, Curr=1.

  1. Next=2. 1.next=null. Prev=1, Curr=2.
  2. Next=3. 2.next=1. Prev=2, Curr=3.
  3. Next=null. 3.next=2. Prev=3, Curr=null. Return Prev (3).
java
public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

⚠️ Common Pitfalls & Tips

Make sure to return prev at the end, as curr will be null.

Visual Pointer Reversal

[1] -> [2] -> [3] -> null p=null, c=1 Iter 1: [1].next=null, p=1, c=2 Iter 2: [2].next=1, p=2, c=3 Iter 3: [3].next=2, p=3, c=null Return p=3: [3] -> [2] -> [1] -> null
← Previous QuestionMerge Two Sorted Lists
Next Question →Middle of the Linked List