🔧 JavaScript Linked List Operations

Pattern 1 — Reverse a Linked List

🧠 How to Approach This

Step 1 — Recognize the pattern: In-place pointer reversal with 3 variables.

Step 2 — Brute force (what NOT to do): Push to array, rebuild — O(n) space.

Step 3 — Optimal insight: prev/curr/next swap loop.

Step 4 — Algorithm:

1. prev = null, curr = head

2. Each step: save next, flip curr.next = prev, advance both

3. Return prev

Step 5 — Edge cases: Empty or single node.

function reverseList(head) {
  let prev = null, curr = head;
  while (curr) {
    const next = curr.next;
    curr.next  = prev;
    prev       = curr;
    curr       = next;
  }
  return prev;
}

Time: O(n) | Space: O(1)

---

Pattern 2 — Find Middle (Slow/Fast)

🧠 How to Approach This

Step 1 — Recognize the pattern: Fast pointer moves 2x, slow moves 1x.

Step 2 — Brute force (what NOT to do): Count, walk n/2 — two passes.

Step 3 — Optimal insight: One pass — when fast hits end, slow is at middle.

Step 4 — Algorithm:

1. slow = fast = head

2. While fast && fast.next: slow++, fast += 2

3. Return slow

Step 5 — Edge cases: Even length returns second middle.

function findMiddle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

Time: O(n) | Space: O(1)

---

Pattern 3 — Detect Cycle

🧠 How to Approach This

Step 1 — Recognize the pattern: If cycle exists, fast pointer laps slow pointer.

Step 2 — Brute force (what NOT to do): Store visited nodes in a Set — O(n) space.

Step 3 — Optimal insight: Floyd's: slow+1, fast+2. They meet inside cycle.

Step 4 — Algorithm:

1. slow = fast = head

2. Advance; if they meet === → cycle

3. Loop exits → no cycle

Step 5 — Edge cases: null or 1 node without self-loop → false.

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Time: O(n) | Space: O(1)

---

Pattern 4 — Merge Two Sorted Lists

🧠 How to Approach This

Step 1 — Recognize the pattern: Two-pointer merge step from merge sort.

Step 2 — Brute force (what NOT to do): Collect, sort, rebuild — O(n log n).

Step 3 — Optimal insight: Compare heads, attach smaller, advance that pointer.

Step 4 — Algorithm:

1. Dummy head

2. While both exist: attach smaller, advance

3. Attach remainder

Step 5 — Edge cases: Either list empty.

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else                  { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 ?? l2;
  return dummy.next;
}

Time: O(n + m) | Space: O(1)

---

Pattern 5 — Remove Nth From End

🧠 How to Approach This

Step 1 — Recognize the pattern: Two pointers with gap of N+1 — one pass.

Step 2 — Brute force (what NOT to do): Count length, walk to position — two passes.

Step 3 — Optimal insight: Advance fast N+1 steps first, then move both until fast = null.

Step 4 — Algorithm:

1. Dummy, fast advances N+1 steps

2. Move both until fast = null

3. slow.next = slow.next.next

Step 5 — Edge cases: Remove head node — dummy handles.

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let slow = dummy, fast = dummy;
  for (let i = 0; i <= n; i++) fast = fast.next;
  while (fast) { slow = slow.next; fast = fast.next; }
  slow.next = slow.next.next;
  return dummy.next;
}

Time: O(n) | Space: O(1)

---

Pattern 6 — Intersection of Two Lists

🧠 How to Approach This

Step 1 — Recognize the pattern: Path equalisation — traverse A+B and B+A.

Step 2 — Brute force (what NOT to do): Store all A nodes in a Set, traverse B.

Step 3 — Optimal insight: a walks A→B, b walks B→A. Equal total distance → meet at intersection.

Step 4 — Algorithm:

1. a = headA, b = headB

2. Advance; switch heads on null

3. Return when a === b

Step 5 — Edge cases: No intersection → both null together.

function getIntersectionNode(headA, headB) {
  let a = headA, b = headB;
  while (a !== b) {
    a = a !== null ? a.next : headB;
    b = b !== null ? b.next : headA;
  }
  return a;
}

Time: O(n + m) | Space: O(1)