🚂 Linked Lists: Advanced Operations

The Train Station Analogy

Imagine a train station where each train car is a node. Each car knows only about the car connected behind it. Today, you’re the Station Master learning powerful tricks to manage your trains!

🔗 Merging Two Sorted Lists

The Story

You have two trains arriving at the station. Each train has cars numbered in order (smallest to largest). Your job? Combine them into ONE perfectly sorted train!

How It Works

Think of it like a zipper. You compare the front car of each train. Whichever is smaller goes first. Then you move to the next car on that train and compare again.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    current = dummy

    while l1 and l2:
        if l1.val <= l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    current.next = l1 or l2
    return dummy.next

Simple Example

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

Merged: 1 → 2 → 3 → 4 → 5 → 6

graph TD
    A[Compare 1 and 2] --> B[Pick 1]
    B --> C[Compare 3 and 2]
    C --> D[Pick 2]
    D --> E[Compare 3 and 4]
    E --> F[Pick 3]
    F --> G[Continue...]

📊 Sort List

The Story

Your train cars are all mixed up! Some have big numbers, some have small. You need to sort them. But here’s the catch — you can only look at one car at a time.

The Magic Trick: Merge Sort

1. Split the train in half
2. Sort each half (split again and again!)
3. Merge the sorted halves together

def sortList(head):
    if not head or not head.next:
        return head

    # Find middle
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Split
    mid = slow.next
    slow.next = None

    # Sort halves
    left = sortList(head)
    right = sortList(mid)

    # Merge!
    return mergeTwoLists(left, right)

Simple Example

Before: 4 → 2 → 1 → 3

1. Split: 4 → 2 and 1 → 3
2. Split more: 4, 2, 1, 3
3. Merge pairs: 2 → 4 and 1 → 3
4. Final merge: 1 → 2 → 3 → 4

🤝 Intersection of Two Lists

The Story

Two trains start from different stations but meet at the same car somewhere along the way. Your mission: Find where they meet!

The Clever Solution

Imagine two friends walking. When one reaches the end, they teleport to the other’s start. If the paths meet, they’ll meet at the same spot!

def getIntersectionNode(headA, headB):
    if not headA or not headB:
        return None

    a, b = headA, headB

    while a != b:
        a = a.next if a else headB
        b = b.next if b else headA

    return a

Simple Example

Train A: 1 → 2 ↘
               → 5 → 6 → 7
Train B:   3 ↗

Intersection at: Node 5

graph TD
    A1[1] --> A2[2]
    B3[3] --> I5[5]
    A2 --> I5
    I5 --> I6[6]
    I6 --> I7[7]

⚖️ Linked List Partitioning

The Story

The Station Master says: “All cars with numbers smaller than X must go to the front. All others go to the back!”

The Solution

Create two mini-trains:

• One for small numbers (less than X)
• One for big numbers (X or more)

Then connect them!

def partition(head, x):
    small_head = ListNode(0)
    big_head = ListNode(0)
    small = small_head
    big = big_head

    while head:
        if head.val < x:
            small.next = head
            small = small.next
        else:
            big.next = head
            big = big.next
        head = head.next

    big.next = None
    small.next = big_head.next
    return small_head.next

Simple Example

Original: 1 → 4 → 3 → 2 → 5 → 2 Partition around: X = 3

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

(All numbers < 3 come first, then the rest)

🎭 Odd Even Linked List

The Story

Time for a dance! All cars at odd positions (1st, 3rd, 5th…) line up first. Then all cars at even positions (2nd, 4th, 6th…) follow.

The Solution

def oddEvenList(head):
    if not head:
        return None

    odd = head
    even = head.next
    even_head = even

    while even and even.next:
        odd.next = even.next
        odd = odd.next
        even.next = odd.next
        even = even.next

    odd.next = even_head
    return head

Simple Example

Original: 1 → 2 → 3 → 4 → 5

Position 1: 1 (odd) Position 2: 2 (even) Position 3: 3 (odd) Position 4: 4 (even) Position 5: 5 (odd)

Result: 1 → 3 → 5 → 2 → 4

graph TD
    O[Odd Group] --> A[1]
    A --> B[3]
    B --> C[5]
    C --> D[2]
    D --> E[4]
    F[Even Group] --> D

🔄 Reorder List

The Story

The Station Master wants a special pattern: First car, then last car, then second car, then second-to-last… like shuffling a deck of cards!

Three Steps

1. Find the middle of the train
2. Reverse the second half
3. Weave them together

def reorderList(head):
    if not head:
        return

    # Step 1: Find middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse second half
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt

    # Step 3: Weave together
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2

Simple Example

Original: 1 → 2 → 3 → 4 → 5

After reorder: 1 → 5 → 2 → 4 → 3

✂️ Remove Nth Node From End

The Story

“Remove the 2nd car from the END!” shouts the Station Master. But you can only walk forward — how do you know where the end is?

The Two-Pointer Trick

Send a scout ahead by N steps. Then move both pointers together. When the scout reaches the end, you’ve found your target!

def removeNthFromEnd(head, n):
    dummy = ListNode(0)
    dummy.next = head
    first = dummy
    second = dummy

    # Move first N+1 steps ahead
    for _ in range(n + 1):
        first = first.next

    # Move both until first hits end
    while first:
        first = first.next
        second = second.next

    # Remove the node
    second.next = second.next.next
    return dummy.next

Simple Example

Original: 1 → 2 → 3 → 4 → 5 Remove: 2nd from end (which is 4)

Result: 1 → 2 → 3 → 5

graph TD
    A[Scout goes 3 steps ahead]
    A --> B[Move both together]
    B --> C[Scout at end]
    C --> D[Pointer at node BEFORE target]
    D --> E[Skip over target!]

🌟 Quick Summary Table

🎉 You Did It!

You’re now a Linked List Station Master! These advanced operations are your tools to manage trains of data like a pro.

Remember: Every operation is just about moving pointers — like changing which car connects to which. Practice these, and you’ll handle any linked list challenge that comes your way! 🚂✨