Day 52: Mastering Linked List Problems – Reverse II, K Group, Reorder & Rotate | Linked List

---

🚀 Introduction

Welcome to Day 52 of my DSA Journey!
After spending an intense few weeks mastering Recursion, I’ve now shifted my focus to one of the most fundamental data structures in DSA — the Linked List.

Transitioning from recursion to linked lists has been a rewarding step, as these concepts are closely connected, especially when tackling problems involving traversal and pointer manipulation.

Over the past 3 days, I’ve solved several key problems on Singly Linked Lists, including: Reverse Linked List II, Reverse Nodes in K Group, Reorder Linked List, and Rotate Linked List.

I’m documenting this journey publicly to stay consistent and to help others who are starting their DSA path from scratch.

Feel free to follow me on Twitter for real-time updates and coding insights!

📅 Here’s What I Covered Over the Last 3 Days:

Day 49

• Reverse Linked List II
• Reverse Nodes in K Group

Day 50

• Reorder Linked List

Day 51

• Rotate Linked List

Let’s dive deeper into these problems below 👇

---

Q 1. Reverse Linked List II

Given the head of a singly linked list and two positions left and right, reverse the nodes of the list from position left to right and return the modified list.

Example:

Input head = 1->2->3->4->5, left = 2, right = 4

Output: 1->4->3->2->5

Only the sublist from position 2 to 4 (2->3->4) is reversed. The rest of the list remains unchanged.

Approach:

1. Traverse the list until the left position to locate the starting point of the sublist.
2. Reverse the nodes between left and right using the standard iterative reversal technique.
3. Reconnect the reversed sublist back to the original list:
   • Connect the node before left to the new head of the reversed sublist.
   • Connect the node after right to the tail of the reversed sublist.
4. Return the updated head.

Code Implementation:

private Node reverseList(Node head, int left, int right) {
    if (head == null || left == right) return head;

    Node prev = null;
    Node curr = head;

    // Step 1: Move curr to the left-th node
    for(int i = 0; curr != null && i < left - 1; i++){
        prev = curr;
        curr = curr.next;
    }

    Node last = prev;
    Node newEnd = curr;
    Node next = null;

    // Step 2: Reverse sublist from left to right
    for(int i = 0; curr != null && i < right - left + 1; i++){
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    // Step 3: Reconnect reversed sublist
    if(last != null) {
        last.next = prev;
    } else {
        head = prev;
    }
    newEnd.next = curr;

    return head;
}

Time & Space Complexity:

• Time Complexity: O(n) → Traverse the list once.
• Space Complexity: O(1) → Only pointers are used, no extra space.

Final Thoughts:

• The key is to carefully track the nodes before, within, and after the sublist.
• This approach reverses the sublist in-place without creating extra nodes.

Edge Cases:

• left = 1 → the head of the list changes.
• left = right → no reversal is needed.

Mastering this pattern helps in many linked list variations, especially interval-based reversals.

---

Q 2. Reverse Nodes in K Group

Given a linked list, reverse the nodes of the list k at a time and return its modified list.
If the number of nodes is not a multiple of k, the last remaining nodes are left as is.

Example:

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

Output:
[2,1,4,3,5]

Explanation:

• First group of 2 → [1,2] becomes [2,1]
• Second group of 2 → [3,4] becomes [4,3]
• Last node [5] is left unchanged since group size < k

Approach:

1. Count nodes: First calculate total number of nodes to check if a group of size k exists.
2. Dummy node: Use a dummy node before head to simplify edge cases.
3. Group reversal:
   • For each group of k, reverse nodes using standard reversal logic.
   • Connect the previous group end to the reversed head.
   • Connect the end of current group to the next group start.
4. Repeat until there are fewer than k nodes left.

Code Implementation:

private static Node reverseKGroups(Node head, int k){
    if(head == null || k <= 1) {
        return head;
    }

    int count = countNode(head);

    Node dummy = new Node(-1);
    dummy.next = head;
    Node prevGroupEnd = dummy;

    while (count >= k){
        Node groupStart = prevGroupEnd.next;
        Node curr = groupStart;

        // Reverse K Nodes
        Node prev = null;
        Node next = null;
        for(int i=0;i<k;i++){
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // Connect reversed group
        prevGroupEnd.next = prev;
        groupStart.next = curr;

        prevGroupEnd = groupStart;
        count -= k;
    }

    return dummy.next;
}

private static int countNode(Node head) {
    Node temp = head;
    int count = 0;
    while (temp != null) {
        count++;
        temp = temp.next;
    }
    return count;
}

Time & Space Complexity:

• Time Complexity: O(n) → Each node is visited once.
• Space Complexity: O(1) → Reversal is done in-place with pointers.

Final Thoughts:

• This problem is an extension of reverse a sublist, but repeated in fixed-size groups.
• Using a dummy node simplifies handling edge cases like reversing the first group.
• Edge Cases:
  • k = 1 → List remains unchanged.
  • k > length of list → Entire list remains unchanged.

Understanding this pattern is very helpful for advanced linked list problems like Reverse Nodes in K Group II or Reverse in Pairs.

---

Q 3. Reorder Linked List

Given the head of a singly linked list. Reorder the list so that the nodes are arranged as:
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...

Example:

Input: 1 → 2 → 3 → 4 → 5

Output: 1 → 5 → 2 → 4 → 3

The reordering should be done in-place without changing the node values.

Approach:

1. Find the middle node → Use slow & fast pointer technique to split the list into two halves.

   • Example: 1 → 2 → 3 → 4 → 5 → mid = 3.

2. Reverse the second half → Reverse the list starting from mid.next.

   • Example: second half 4 → 5 becomes 5 → 4.

3. Merge both halves alternately →

   • Take one node from the first half, then one from the second half.
   • Continue until all nodes are merged.

Code Implementation:

private void reorderList(Node head){
    if(head == null || head.next == null) return;

    Node mid = getMid(head);

    Node second = reverseList(mid.next);
    Node first = head;

    while(second != null) {
        Node temp = first.next;
        first.next = second;
        first = temp;

        temp = second.next;
        second.next = first;
        second = temp;
    }

    first.next = null;
}

private Node reverseList(Node node) {
    Node prev = null;
    Node curr = node;

    while (curr != null) {
        Node next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

private Node getMid(Node node) {
    Node slow = node;
    Node fast = node;

    while (fast != null && fast.next != null && fast.next.next != null ){
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

Time & Space Complexity:

• Time Complexity: O(n) → One pass to find mid, one pass to reverse, one pass to merge.
• Space Complexity: O(1) → In-place rearrangement using only pointers.

Final Thoughts:

This problem combines three essential linked list techniques:

• Finding the middle node
• Reversing a linked list
• Merging two linked lists alternately

Understanding this pattern helps in solving advanced linked list rearrangement problems.

---

Q 4. Rotate Linked List

Given the head of a linked list, rotate the list to the right by k places.

Example:

Input DLL: 1 → 2 → 3 → 4 → 5, k = 2

Output DLL: 4 → 5 → 1 → 2 → 3

Here, the last 2 nodes move to the front while maintaining their order.

Approach:

1. Find the length & tail → Traverse the list to calculate its length and get the tail node.
2. Normalize k → Since rotating by len gives the same list, use k = k % len.
3. Find new head → Traverse (len - k) steps to locate the new head.
4. Reconnect nodes →
   • Make the old tail point to the old head (circular list).
   • Break the link before the new head.

Code Implementation:

private static Node rotateList(Node head, int k) {
    if(head == null || head.next == null || k == 0){
        return head;
    }
    int len = 1;
    Node tail = head;
    while (tail.next != null) {
        len++;
        tail = tail.next;
    }

    k = k % len;
    if(k == 0) {
        return head;
    }

    Node prev = null;
    Node newHead = head;
    for(int i=0; i < len - k; i++) {
        prev = newHead;
        newHead = newHead.next;
    }

    tail.next = head;
    if(prev != null) {
        prev.next = null;
    }

    return newHead;
}

Time & Space Complexity:

• Time Complexity: O(n) → One traversal to find length, one to find new head.
• Space Complexity: O(1) → No extra space, only pointers used.

Final Thoughts:

This problem highlights rotation logic using modular arithmetic.

Key steps:

• Connect the list into a cycle
• Break at the right position

Edge Cases:

• k = 0 → No rotation
• k % len = 0 → List remains unchanged

This is a great practice for pointer manipulation and understanding cyclic linked lists.

---

5. What's next:

I’m excited to keep growing and sharing along the way! Here’s what’s coming up:

• Posting new blog updates every 3 days to share what I’m learning and building.
• Alongside mastering DSA concepts, I’m also documenting my web development journey — check out my ongoing Web dev Journey Blog for ReactJS concepts, UI projects, Codes, and more.
• Sharing regular progress and insights on X (Twitter) — feel free to follow me there and join the conversation!

Thanks for being part of this journey!

---

6. Conclusion:

Over the past few days, I tackled some of the most fundamental yet tricky Linked List problems — from reversing sublists, handling groups, and reordering, to rotating the list.

Here’s what I learned and reinforced along the way:

• Pointer manipulation is everything in linked list problems.
• Breaking problems into smaller steps (find mid → reverse → merge) makes even the toughest ones manageable.
• Many problems share common techniques (reversal, dummy nodes, slow/fast pointers), so recognizing patterns is the real superpower.
• Edge cases (like small k, list length mismatches, or single nodes) can make or break your solution.

These problems not only sharpen problem-solving skills but also build confidence for tackling advanced linked list variations and interview-level challenges.

If you're on a similar learning path, feel free to follow along or reach out — let’s grow together.