DEV Community

Dev Cookies
Dev Cookies

Posted on

🚀 Day 6: In-place Reversal of a Linked List (Amazon Interview Series)

Reversing a linked list (or part of it) in-place is a fundamental skill. Amazon often builds larger problems on this small trick — like reversing sublists, checking palindromes, or rotating lists.

The main idea:

  • Use three pointers (prev, curr, next)
  • Iteratively reverse curr.next → prev
  • Move forward until the list is reversed

🔑 When to Use This Pattern?

  • Reverse a whole linked list
  • Reverse a portion of a list (between left & right indices)
  • Reverse in groups of k (Amazon favorite!)
  • Check if a linked list is a palindrome
  • Reorder linked list problems

📝 Problem 1: Reverse a Linked List

👉 Amazon-style phrasing:
Reverse a singly linked list in place and return the new head.

Java Solution 

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class ReverseLinkedList {
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(n)
✅ Space Complexity: O(1)

📝 Problem 2: Reverse Sublist (Between Left & Right)

👉 Amazon-style phrasing:
Given a linked list and two positions left and right, reverse the nodes between them.

Java Solution 

public class ReverseSublist {
    public static ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) return null;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;

        // Step 1: move prev to node before "left"
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }

        // Step 2: reverse from left to right
        ListNode curr = prev.next;
        for (int i = 0; i < right - left; i++) {
            ListNode temp = curr.next;
            curr.next = temp.next;
            temp.next = prev.next;
            prev.next = temp;
        }

        return dummy.next;
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Common trick: reverse by pulling nodes out one by one.
✅ Asked frequently by Amazon for list manipulation.

📝 Problem 3: Reverse Nodes in k-Group

👉 Amazon-style phrasing:
Given a linked list, reverse nodes in groups of k. If the number of nodes isn’t a multiple of k, leave the remainder as is.

Java Solution 

public class ReverseKGroup {
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy, curr = dummy, next = dummy;

        // Count length
        int count = 0;
        while (curr.next != null) {
            curr = curr.next;
            count++;
        }

        // Reverse in groups
        while (count >= k) {
            curr = prev.next;
            next = curr.next;
            for (int i = 1; i < k; i++) {
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
                next = curr.next;
            }
            prev = curr;
            count -= k;
        }

        return dummy.next;
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Time Complexity: O(n)
✅ Amazon often twists this with k = 2 (pair swapping) or merging it with scheduling/rotation problems.

📝 Problem 4: Palindrome Linked List

👉 Amazon-style phrasing:
Check if a linked list is a palindrome using O(1) extra space.

Approach

  1. Find middle using fast/slow pointers
  2. Reverse second half in place
  3. Compare halves
  4. Restore list if needed

Java Solution 

public class PalindromeLinkedList {
    public static boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // Step 1: find middle
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: reverse second half
        ListNode secondHalf = reverse(slow);
        ListNode copySecondHalf = secondHalf; // to restore later

        // Step 3: compare
        ListNode firstHalf = head;
        while (secondHalf != null) {
            if (firstHalf.val != secondHalf.val) return false;
            firstHalf = firstHalf.next;
            secondHalf = secondHalf.next;
        }

        // Step 4: restore
        reverse(copySecondHalf);
        return true;
    }

    private static ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Elegant combo of Fast & Slow pointers + In-place reversal.

📚 Extended Amazon Practice Problems

  • Rotate Linked List – Shift list right by k places
  • Swap Nodes in Pairs – Reverse sublist of size 2
  • Reverse Alternate k Nodes – Variation of reverseKGroup
  • Flatten a Multilevel Doubly Linked List – Uses same reversal manipulation

🎯 Key Takeaways

  • Reversal is the foundation of many linked list problems.
  • Use three pointers consistently (prev, curr, next).
  • Amazon loves combining Fast & Slow + Reversal for tricky questions.

📅 Next in the series (Day 7):
👉 Tree BFS Pattern – Level order traversal, zigzag traversal, and "right side view" of a tree (Amazon favorites).

Top comments (0)