🔗 Linked Lists: Advanced Operations

The Train Station Story 🚂

Imagine you’re the Station Master at a magical train station. Your trains aren’t normal—they’re made of cars that can connect, disconnect, and rearrange themselves!

Each train car is a node in our linked list:

• The cargo is your data
• The coupler connecting to the next car is your pointer

Today, you’ll learn 7 powerful tricks to manage your train yard like a pro!

🎯 What You’ll Master

graph LR
    A[Advanced Operations] --> B[Merging Sorted Lists]
    A --> C[Sorting a List]
    A --> D[Finding Intersections]
    A --> E[Partitioning]
    A --> F[Odd-Even Rearrange]
    A --> G[Reorder List]
    A --> H[Remove Nth from End]

1️⃣ Merging Two Sorted Lists

The Story

Two trains arrive at your station. Each train has cars arranged from lightest to heaviest. Your job? Combine them into ONE train, keeping everything in order!

How It Works

Think of it like shuffling two sorted card decks:

1. Look at the front card of each deck
2. Pick the smaller one
3. Add it to your new pile
4. Repeat!

Visual Example

Train A: [1] → [3] → [5]
Train B: [2] → [4] → [6]

Step 1: Compare 1 vs 2 → Take 1
Step 2: Compare 3 vs 2 → Take 2
Step 3: Compare 3 vs 4 → Take 3
...and so on!

Result: [1] → [2] → [3] → [4] → [5] → [6]

Java Code

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode current = dummy;

    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    current.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

💡 Key Insight

We use a dummy node as a placeholder. It’s like having an empty engine car at the front—makes attaching the first real car super easy!

2️⃣ Sort List

The Story

A train arrives with cars in random order! You need to sort them from lightest to heaviest. But here’s the catch—you can only move one car at a time!

The Magic Trick: Merge Sort

Think of it like sorting a messy bookshelf:

1. Split the books into two piles
2. Split each pile again (keep going until single books)
3. Merge them back in order!

graph TD
    A["[4,2,1,3]"] --> B["[4,2]"]
    A --> C["[1,3]"]
    B --> D["[4]"]
    B --> E["[2]"]
    C --> F["[1]"]
    C --> G["[3]"]
    D --> H["[2,4]"]
    E --> H
    F --> I["[1,3]"]
    G --> I
    H --> J["[1,2,3,4]"]
    I --> J

Java Code

ListNode sortList(ListNode head) {
    if (head == null || head.next == null)
        return head;

    // Find middle using slow-fast pointers
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    ListNode mid = slow.next;
    slow.next = null;  // Split the list!

    // Sort both halves and merge
    return merge(sortList(head), sortList(mid));
}

💡 Key Insight

Finding the middle uses the turtle-and-rabbit trick! The slow pointer moves 1 step, the fast moves 2 steps. When fast reaches the end, slow is at the middle!

3️⃣ Intersection of Two Lists

The Story

Two train tracks start from different stations but merge at some point! Your job is to find where they meet.

The Clever Solution

Imagine two runners on different paths that eventually merge:

• Runner A’s path: a1 → a2 → c1 → c2
• Runner B’s path: b1 → b2 → b3 → c1 → c2

The trick: When Runner A finishes, they teleport to Runner B’s start. When Runner B finishes, they teleport to Runner A’s start!

They’ll meet at the intersection! 🤯

Visual Example

List A:     a1 → a2 ↘
                      c1 → c2 → c3
List B: b1 → b2 → b3 ↗

After pointer magic:
A walks: a1 → a2 → c1 → c2 → c3 → b1 → b2 → b3 → c1 ✓
B walks: b1 → b2 → b3 → c1 → c2 → c3 → a1 → a2 → c1 ✓
                                      They meet at c1!

Java Code

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;

    ListNode a = headA;
    ListNode b = headB;

    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }

    return a;  // Either intersection or null
}

💡 Key Insight

Both pointers travel the same total distance! This guarantees they’ll meet at the intersection (or both reach null if there’s none).

4️⃣ Linked List Partitioning

The Story

Your train has cars with different weights. A VIP guest wants all cars lighter than X to be in front, and heavier or equal to be in back!

The Simple Approach

Create TWO mini-trains:

1. Light train: All cars < X
2. Heavy train: All cars ≥ X
3. Connect light train to heavy train!

Visual Example

Original: [1] → [4] → [3] → [2] → [5]
Pivot X = 3

Light train: [1] → [2]
Heavy train: [4] → [3] → [5]

Result: [1] → [2] → [4] → [3] → [5]

Java Code

ListNode partition(ListNode head, int x) {
    ListNode lightHead = new ListNode(0);
    ListNode heavyHead = new ListNode(0);
    ListNode light = lightHead;
    ListNode heavy = heavyHead;

    while (head != null) {
        if (head.val < x) {
            light.next = head;
            light = light.next;
        } else {
            heavy.next = head;
            heavy = heavy.next;
        }
        head = head.next;
    }

    heavy.next = null;  // Important!
    light.next = heavyHead.next;
    return lightHead.next;
}

💡 Key Insight

Setting heavy.next = null is crucial! Without it, you might accidentally create a cycle (a train chasing its own tail)!

5️⃣ Odd Even Linked List

The Story

Your train cars are numbered 1, 2, 3, 4, 5… A quirky passenger wants all odd-numbered positions first, then all even-numbered positions!

Note: We’re talking about POSITION (1st, 2nd, 3rd), not the VALUE in the car!

Visual Example

Original: [1] → [2] → [3] → [4] → [5]
Position:  1     2     3     4     5

Odd positions:  [1] → [3] → [5]
Even positions: [2] → [4]

Result: [1] → [3] → [5] → [2] → [4]

Java Code

ListNode oddEvenList(ListNode head) {
    if (head == null) return null;

    ListNode odd = head;
    ListNode even = head.next;
    ListNode evenHead = even;  // Save this!

    while (even != null && even.next != null) {
        odd.next = even.next;   // Skip to next odd
        odd = odd.next;
        even.next = odd.next;   // Skip to next even
        even = even.next;
    }

    odd.next = evenHead;  // Connect odd tail to even head
    return head;
}

💡 Key Insight

We maintain TWO separate chains and weave through the list, picking every other element for each chain!

6️⃣ Reorder List

The Story

A train arrives as: [1] → [2] → [3] → [4] → [5]

The conductor wants a zigzag pattern: first, last, second, second-last, and so on!

Result: [1] → [5] → [2] → [4] → [3]

The Three-Step Magic

1. Find the middle (turtle-rabbit trick!)
2. Reverse the second half
3. Merge alternately

Visual Walkthrough

Step 1: Find middle
[1] → [2] → [3] | [4] → [5]

Step 2: Reverse second half
First half:  [1] → [2] → [3]
Second half: [5] → [4]

Step 3: Merge alternately
[1] → [5] → [2] → [4] → [3]

Java Code

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

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

    // Step 2: Reverse second half
    ListNode second = reverse(slow.next);
    slow.next = null;

    // Step 3: Merge alternately
    ListNode first = head;
    while (second != null) {
        ListNode tmp1 = first.next;
        ListNode tmp2 = second.next;
        first.next = second;
        second.next = tmp1;
        first = tmp1;
        second = tmp2;
    }
}

💡 Key Insight

This combines THREE fundamental techniques into one elegant solution!

7️⃣ Remove Nth Node From End

The Story

Someone wants to remove the 3rd car from the END of your train. But you can only see one car at a time from the front!

The Two-Pointer Dance

Use two runners with a fixed gap!

1. Put Runner A and Runner B at the start
2. Move Runner A forward by N steps
3. Now move BOTH together
4. When Runner A reaches the end, Runner B is at the target!

Visual Example

Remove 2nd from end in: [1] → [2] → [3] → [4] → [5]

Step 1: Move fast pointer 2 steps ahead
        [1] → [2] → [3] → [4] → [5]
         ↑           ↑
        slow       fast

Step 2: Move both until fast reaches end
        [1] → [2] → [3] → [4] → [5]
                     ↑           ↑
                    slow       fast

Step 3: Remove node after slow (which is [4])
Result: [1] → [2] → [3] → [5]

Java Code

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode fast = dummy;
    ListNode slow = dummy;

    // Move fast n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // Move both until fast reaches end
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // Remove the node
    slow.next = slow.next.next;
    return dummy.next;
}

💡 Key Insight

The dummy node helps handle edge cases, like removing the first node!

🏆 Summary: Your Toolkit

🎉 You Did It!

You’ve learned 7 powerful techniques for manipulating linked lists. These patterns appear everywhere in coding interviews and real-world applications!

Remember: Every complex operation is just a clever combination of:

• Finding the middle (slow-fast pointers)
• Reversing a portion
• Merging lists
• Using dummy nodes

Now go practice these on real problems! 🚀