🔗 Linked Lists: Advanced Operations

The Train Yard Adventure

Imagine you’re the manager of a magical train yard. Each train car (node) is connected to the next by a special hook (pointer). Today, you’ll learn the secret tricks that master train conductors use to reorganize, merge, and transform their trains!

🚂 Our Universal Analogy: The Train Yard

Throughout this guide:

• Node = A train car carrying cargo (data)
• Pointer/Next = The hook connecting cars together
• Head = The engine at the front
• Null = End of the track (no more cars)

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

1. Merging Two Sorted Lists 🔀

The Story

Two trains arrive at your yard, each already organized from smallest to biggest cargo numbers. Your job? Combine them into ONE perfectly sorted train!

The Magic Trick

Use a dummy engine at the front. Compare the first cars of both trains, attach the smaller one, then move forward. Repeat!

graph TD
    A["Start with Dummy"] --> B{Compare Front Cars}
    B -->|L1 smaller| C["Attach L1's car]
    B -->|L2 smaller| D[Attach L2's car"]
    C --> E["Move L1 forward"]
    D --> F["Move L2 forward"]
    E --> B
    F --> B
    B -->|One train empty| G["Attach remaining cars"]
    G --> H["Return dummy.next"]

The Code

function mergeTwoLists(l1, l2) {
  let dummy = new Node(0);
  let current = dummy;

  while (l1 && 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 || l2;
  return dummy.next;
}

Example

Train 1: 1 → 3 → 5 Train 2: 2 → 4 → 6 Result: 1 → 2 → 3 → 4 → 5 → 6 ✨

Why it works: We never go backwards! Each comparison takes the smallest available car.

2. Sort List 📊

The Story

A messy train arrives with cars in random order! You need to sort it, but here’s the catch: you can only see one car at a time and must work efficiently.

The Secret: Merge Sort

1. Split the train in half using the slow/fast pointer trick
2. Sort each half (recursively)
3. Merge the sorted halves

graph TD
    A["4→2→1→3"] --> B["Split in half"]
    B --> C["4→2"]
    B --> D["1→3"]
    C --> E["Split"]
    D --> F["Split"]
    E --> G["4"]
    E --> H["2"]
    F --> I["1"]
    F --> J["3"]
    G --> K["Merge: 2→4"]
    H --> K
    I --> L["Merge: 1→3"]
    J --> L
    K --> M["Final Merge: 1→2→3→4"]
    L --> M

Finding the Middle

function getMiddle(head) {
  let slow = head;
  let fast = head.next;

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

Complete Sort

function sortList(head) {
  if (!head || !head.next) return head;

  let mid = getMiddle(head);
  let right = mid.next;
  mid.next = null;

  let leftSorted = sortList(head);
  let rightSorted = sortList(right);

  return mergeTwoLists(leftSorted, rightSorted);
}

Example

Before: 4 → 2 → 1 → 3 After: 1 → 2 → 3 → 4 ✨

3. Intersection of Two Lists ✂️

The Story

Two trains start from different stations but join at the same car later! Find where they meet.

The Clever Trick

If Train A finishes, jump to Train B’s start. If Train B finishes, jump to Train A’s start. They’ll meet at the intersection!

graph TD
    A["Start both pointers"] --> B{Both reach same node?}
    B -->|No| C["Move each forward"]
    C --> D{Pointer reached end?}
    D -->|Yes| E[Jump to other list's head]
    D -->|No| B
    E --> B
    B -->|Yes or both null| F["Return intersection"]

The Code

function getIntersection(headA, headB) {
  if (!headA || !headB) return null;

  let pA = headA;
  let pB = headB;

  while (pA !== pB) {
    pA = pA ? pA.next : headB;
    pB = pB ? pB.next : headA;
  }

  return pA;
}

Why This Works

Math magic! If A has length a + c and B has length b + c (where c is shared), then:

• Pointer A travels: a + c + b
• Pointer B travels: b + c + a
• Same total = they meet at intersection!

Example

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

Intersection: Node 6 ✨

4. Linked List Partitioning 📦

The Story

You need to rearrange a train so all cars with numbers less than X come before cars with numbers X or greater. Order within groups doesn’t matter!

The Approach

Create two temporary trains:

• Small train: All cars < X
• Big train: All cars >= X

Then connect them!

graph TD
    A["Original: 1→4→3→2→5→2"] --> B["Partition around X=3"]
    B --> C["Small: 1→2→2"]
    B --> D["Big: 4→3→5"]
    C --> E["Connect: 1→2→2→4→3→5"]
    D --> E

The Code

function partition(head, x) {
  let smallHead = new Node(0);
  let bigHead = new Node(0);
  let small = smallHead;
  let big = bigHead;

  while (head) {
    if (head.val < x) {
      small.next = head;
      small = small.next;
    } else {
      big.next = head;
      big = big.next;
    }
    head = head.next;
  }

  big.next = null;
  small.next = bigHead.next;

  return smallHead.next;
}

Example

Before: 1 → 4 → 3 → 2 → 5 → 2 (X = 3) After: 1 → 2 → 2 → 4 → 3 → 5 ✨

5. Odd Even Linked List 🔢

The Story

Reorganize your train so cars at odd positions (1st, 3rd, 5th…) come first, followed by cars at even positions (2nd, 4th, 6th…).

The Trick

Use two pointers to build two separate chains, then join them!

graph TD
    A["1→2→3→4→5"] --> B["Separate by position"]
    B --> C["Odd: 1→3→5"]
    B --> D["Even: 2→4"]
    C --> E["Join: 1→3→5→2→4"]
    D --> E

The Code

function oddEvenList(head) {
  if (!head || !head.next) return head;

  let odd = head;
  let even = head.next;
  let evenHead = even;

  while (even && even.next) {
    odd.next = even.next;
    odd = odd.next;
    even.next = odd.next;
    even = even.next;
  }

  odd.next = evenHead;
  return head;
}

Example

Before: 1 → 2 → 3 → 4 → 5 Odd positions: 1 → 3 → 5 Even positions: 2 → 4 After: 1 → 3 → 5 → 2 → 4 ✨

6. Reorder List 🔄

The Story

Transform L0 → L1 → ... → Ln into L0 → Ln → L1 → Ln-1 → L2 → ...

It’s like shuffling cards: take from the top, then the bottom, alternating!

The Three Steps

1. Find the middle (slow/fast pointers)
2. Reverse the second half
3. Weave the two halves together

graph TD
    A["1→2→3→4→5"] --> B["Find Middle"]
    B --> C["First: 1→2→3"]
    B --> D["Second: 4→5"]
    D --> E["Reverse: 5→4"]
    C --> F["Weave together"]
    E --> F
    F --> G["1→5→2→4→3"]

The Code

function reorderList(head) {
  if (!head || !head.next) return;

  // Find middle
  let slow = head, fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }

  // Reverse second half
  let prev = null, curr = slow.next;
  slow.next = null;
  while (curr) {
    let next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // Weave together
  let first = head, second = prev;
  while (second) {
    let tmp1 = first.next;
    let tmp2 = second.next;
    first.next = second;
    second.next = tmp1;
    first = tmp1;
    second = tmp2;
  }
}

Example

Before: 1 → 2 → 3 → 4 → 5 After: 1 → 5 → 2 → 4 → 3 ✨

7. Remove Nth Node From End 🎯

The Story

Remove the car that’s N positions from the back without counting all cars first!

The Two-Pointer Dance

Send a scout (fast pointer) ahead by N steps. Then move both pointers together. When scout reaches the end, the slow pointer is right before the target!

graph TD
    A["Start: both at head"] --> B["Move fast N steps ahead"]
    B --> C["Move both together"]
    C --> D{Fast at end?}
    D -->|No| C
    D -->|Yes| E["Slow is before target"]
    E --> F["Skip the target node"]

The Code

function removeNthFromEnd(head, n) {
  let dummy = new Node(0);
  dummy.next = head;
  let fast = dummy;
  let slow = dummy;

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

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

  // Skip the nth node
  slow.next = slow.next.next;

  return dummy.next;
}

Example

List: 1 → 2 → 3 → 4 → 5, N = 2 Remove: 4 (2nd from end) Result: 1 → 2 → 3 → 5 ✨

Why Dummy Node?

Edge case! If we need to remove the first node, having a dummy before it saves us from special handling.

🎓 Key Takeaways

🚀 You Did It!

You’ve mastered the 7 advanced linked list operations! These aren’t just algorithms—they’re thinking patterns you’ll use everywhere:

• Dummy nodes simplify edge cases
• Two pointers solve problems without extra space
• Divide and conquer handles complex sorting
• Reverse and weave creates elegant transformations

Now go build something amazing! 🎉