🔗 Linked List

One-line summary: A dynamic chain of nodes — O(1) insert/delete at known position, O(n) access by index. Master reversal, cycle detection, and merge patterns.

---

Concept

Each node: val + next pointer (singly), or prev+next (doubly).

Types: Singly, Doubly, Circular.

---

Diagram

---

Time & Space Complexity

Operation	Time	Space
Access by index	O(n)	O(1)
Insert/Delete at head	O(1)	O(1)
Reverse	O(n)	O(1)
Cycle detection (Floyd's)	O(n)	O(1)
Find middle	O(n)	O(1)

---

Common Patterns

Reverse (Iterative)

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

Cycle Detection (Floyd's)

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;
}

Find Middle

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

Merge Two Sorted Lists

function mergeTwoLists(l1, l2) {
  const dummy = { next: null };
  let cur = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) {
      cur.next = l1;
      l1 = l1.next;
    } else {
      cur.next = l2;
      l2 = l2.next;
    }
    cur = cur.next;
  }
  cur.next = l1 || l2;
  return dummy.next;
}

---

Pitfalls

• Losing reference to next before reassigning — store it first
• Forgetting to update tail.next = null after reversal
• Off-by-one in middle finding: even-length list has two middles

---

Practice Problems

Problem	Difficulty	Solution
LC 206 — Reverse Linked List	Easy
LC 160 — Intersection of Two Linked Lists	Easy
LC 141 — Linked List Cycle	Easy
LC 876 — Middle of the Linked List	Easy
LC 19 — Remove Nth Node From End	Medium
LC 143 — Reorder List	Medium
LC 234 — Palindrome Linked List	Easy
LC 25 — Reverse Nodes in k-Group	Hard
LC 138 — Copy List with Random Pointer	Medium
CC — Linked List Operations (LISTOPS)	Medium
LC 2 — Add Two Numbers	Medium
LC 21 — Merge Two Sorted Lists	Easy
LC 83 — Remove Duplicates from Sorted List	Easy
LC 203 — Remove Linked List Elements	Easy
LC 237 — Delete Node in a Linked List	Easy
LC 1290 — Convert Binary Number in a Linked List to Integer	Easy
LC 1474 — Delete N Nodes After M Nodes of a Linked List	Easy
LC 24 — Swap Nodes in Pairs	Medium
LC 61 — Rotate List	Medium
LC 82 — Remove Duplicates from Sorted List II	Medium
LC 86 — Partition List	Medium
LC 92 — Reverse Linked List II	Medium
LC 142 — Linked List Cycle II	Medium
LC 147 — Insertion Sort List	Medium
LC 148 — Sort List	Medium
LC 328 — Odd Even Linked List	Medium
LC 445 — Add Two Numbers II	Medium
LC 725 — Split Linked List in Parts	Medium
LC 817 — Linked List Components	Medium
LC 1019 — Next Greater Node In Linked List	Medium
LC 1367 — Linked List in Binary Tree	Medium
LC 1721 — Swapping Nodes in a Linked List	Medium
CC — Linked List Operations (LISTOPS)	Medium
CC — Reverse Linked List (REVLIST)	Medium
CC — Merge Sorted Lists (MERGESORT)	Medium
LC 23 — Merge k Sorted Lists	Hard
LC 146 — LRU Cache	Hard
LC 460 — LFU Cache	Hard
LC 1206 — Design Skiplist	Hard
CC — Advanced Linked List (ADVLIST)	Hard

---

Related Topics

• Two Pointers — fast/slow is a linked-list technique
• Stack — LRU = doubly linked list + hash map
• Trees — tree nodes are linked nodes with more pointers

← Back to Home · © sparshjaswal