← Back to All Patterns

In-place Linked List Reversal

🔗 Linked List Reversal Animation

1
2
3
4
Previous
null
Current
null
Next
null

Original: 1 → 2 → 3 → 4 → null

Step 1 of 6

🎯 Explain Like I'm 5...

Imagine a train 🚂 with 4 cars holding hands in a line: Car1 holds Car2's hand, Car2 holds Car3's hand, and Car3 holds Car4's hand!

🔄 Reversing the Train: Make everyone turn around and hold the OTHER person's hand!

  • • Start: 1→2→3→4 (everyone facing right →)
  • • Tell Car1: "Turn around! Hold nobody's hand now"
  • • Tell Car2: "Turn around! Hold Car1's hand instead"
  • • Tell Car3: "Turn around! Hold Car2's hand instead"
  • • Tell Car4: "Turn around! Hold Car3's hand instead"

Result: 4→3→2→1 (everyone facing left ←, train reversed!) 🎉

🚀 The Trick: Use 3 helpers to remember: previous car, current car, and next car. Change one connection at a time! It's like making a chain of friends turn around one by one! 🔗

When Should You Use This Pattern?

  • ✓Reversing an entire linked list
  • ✓Reversing part of a linked list (sublist)
  • ✓Reversing every K nodes
  • ✓Need O(1) space solution (in-place)

📝 Example 1: Reverse Entire Linked List

Given 1 → 2 → 3 → 4 → 5, reverse it to 5 → 4 → 3 → 2 → 1.

Step-by-Step Thinking:

  1. Keep track of: previous (null), current (head), next (null)
  2. For each node: save next, reverse pointer, move forward
  3. Current.next = previous (reverse the arrow!)
  4. Move: previous = current, current = next
  5. Return previous (new head)
ReverseLinkedList.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}
public class ReverseLinkedList {
    public static ListNode reverse(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
        while (current != null) {
            // Save next node before changing pointer
            ListNode next = current.next;
            // Reverse the pointer
            current.next = previous;
            // Move forward
            previous = current;
            current = next;
        }
        return previous;  // New head
    }
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        // Create list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        System.out.print("Original: ");
        printList(head);
        head = reverse(head);
        System.out.print("Reversed: ");
        printList(head);
        // Output: 5 -> 4 -> 3 -> 2 -> 1
    }
}

📝 Example 2: Reverse Sublist (from position m to n)

Given 1 → 2 → 3 → 4 → 5 and m=2, n=4, reverse positions 2-4 to get 1 → 4 → 3 → 2 → 5.

ReverseSublist.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public class ReverseSublist {
    public static ListNode reverseBetween(ListNode head, int m, int n) {
        if (head == null || m == n) {
            return head;
        }
        // Create dummy node to handle edge cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        // Move to node before position m
        for (int i = 1; i < m; i++) {
            prev = prev.next;
        }
        // Start reversing from position m to n
        ListNode current = prev.next;
        ListNode next = null;
        for (int i = 0; i < n - m; i++) {
            next = current.next;
            current.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        return dummy.next;
    }
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        // Create list: 1 -> 2 -> 3 -> 4 -> 5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        System.out.print("Original: ");
        printList(head);
        head = reverseBetween(head, 2, 4);
        System.out.print("After reversing positions 2-4: ");
        printList(head);
        // Output: 1 -> 4 -> 3 -> 2 -> 5
    }
}

📝 Example 3: Reverse Every K Nodes

Given 1 → 2 → 3 → 4 → 5 → 6 and k=2, reverse every 2 nodes: 2 → 1 → 4 → 3 → 6 → 5.

ReverseKGroup.java
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
public class ReverseKGroup {
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) {
            return head;
        }
        // Count total nodes
        int count = 0;
        ListNode current = head;
        while (current != null) {
            count++;
            current = current.next;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        // Reverse k nodes at a time
        while (count >= k) {
            current = prev.next;
            ListNode next = current.next;
            // Reverse k nodes
            for (int i = 1; i < k; i++) {
                current.next = next.next;
                next.next = prev.next;
                prev.next = next;
                next = current.next;
            }
            prev = current;
            count -= k;
        }
        return dummy.next;
    }
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) System.out.print(" -> ");
            head = head.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        // Create list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        System.out.print("Original: ");
        printList(head);
        head = reverseKGroup(head, 2);
        System.out.print("After reversing every 2 nodes: ");
        printList(head);
        // Output: 2 -> 1 -> 4 -> 3 -> 6 -> 5
    }
}

🔑 Key Points to Remember

  • 1️⃣Three pointers: previous, current, next
  • 2️⃣Always save next before changing current.next
  • 3️⃣Time Complexity: O(n) - visit each node once
  • 4️⃣Space Complexity: O(1) - only a few pointers!

💪 Practice Problems

  • • Reverse Nodes in k-Group
  • • Swap Nodes in Pairs
  • • Rotate List
  • • Reverse Linked List II
  • • Palindrome Linked List