Linked Lists: Dynamic Sequential Data Structures

Introduction

Linked lists are one of the most important data structures in computer science. Unlike arrays, which store elements in contiguous memory, linked lists use nodes connected by pointers, making insertions and deletions highly efficient.

Understanding linked lists is critical for coding interviews — they test your ability to manipulate pointers, handle edge cases, and think about memory. Many classic interview problems (reversing a list, detecting cycles, merging sorted lists) rely on linked list mastery.

What You'll Learn

✅ Understand how linked lists work internally
✅ Implement singly and doubly linked lists from scratch
✅ Master pointer manipulation techniques
✅ Apply Fast & Slow pointer pattern
✅ Reverse linked lists iteratively and recursively
✅ Solve classic interview problems step-by-step

Prerequisites

Understanding of Big O Notation & Complexity Analysis
Familiarity with Problem-Solving Patterns
Completed Arrays & Strings
Basic programming knowledge in TypeScript or Python

1. What is a Linked List?

A linked list is a linear data structure where each element (called a node) contains:

Data — the value stored
Pointer(s) — reference(s) to the next (and possibly previous) node

Unlike arrays, linked list nodes are scattered throughout memory and connected via pointers.

Arrays vs Linked Lists

Array (contiguous memory):

Linked List (scattered memory):

Key Trade-offs

Operation	Array	Linked List
Access by index	O(1)	O(n)
Insert at beginning	O(n)	O(1)
Insert at end	O(1)*	O(n)† / O(1)‡
Insert at middle	O(n)	O(1)§
Delete at beginning	O(n)	O(1)
Delete at middle	O(n)	O(1)§
Search	O(n)	O(n)
Memory	Contiguous, compact	Scattered, extra pointer overhead

*Amortized for dynamic arrays | †Without tail pointer | ‡With tail pointer | §If you already have the node reference

When to use linked lists over arrays:

Frequent insertions/deletions at the beginning
Unknown size (no need to resize)
No need for random access by index
Implementing stacks, queues, or hash table chaining

2. Singly Linked List

The simplest form — each node points to the next node, and the last node points to null.

Node Structure

// TypeScript - Singly Linked List Node
class ListNode<T> {
  val: T;
  next: ListNode<T> | null;
 
  constructor(val: T, next: ListNode<T> | null = null) {
    this.val = val;
    this.next = next;
  }
}

# Python - Singly Linked List Node
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Full Implementation

// TypeScript - Singly Linked List
class SinglyLinkedList<T> {
  head: ListNode<T> | null = null;
  size: number = 0;
 
  // Insert at the beginning - O(1)
  prepend(val: T): void {
    const newNode = new ListNode(val, this.head);
    this.head = newNode;
    this.size++;
  }
 
  // Insert at the end - O(n)
  append(val: T): void {
    const newNode = new ListNode(val);
 
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }
 
  // Insert at specific position - O(n)
  insertAt(val: T, index: number): void {
    if (index < 0 || index > this.size) {
      throw new Error("Index out of bounds");
    }
    if (index === 0) {
      this.prepend(val);
      return;
    }
 
    const newNode = new ListNode(val);
    let current = this.head;
    for (let i = 0; i < index - 1; i++) {
      current = current!.next;
    }
    newNode.next = current!.next;
    current!.next = newNode;
    this.size++;
  }
 
  // Delete by value - O(n)
  delete(val: T): boolean {
    if (!this.head) return false;
 
    // If head node holds the value
    if (this.head.val === val) {
      this.head = this.head.next;
      this.size--;
      return true;
    }
 
    let current = this.head;
    while (current.next) {
      if (current.next.val === val) {
        current.next = current.next.next;
        this.size--;
        return true;
      }
      current = current.next;
    }
    return false;
  }
 
  // Delete at index - O(n)
  deleteAt(index: number): T {
    if (index < 0 || index >= this.size) {
      throw new Error("Index out of bounds");
    }
 
    let removedVal: T;
    if (index === 0) {
      removedVal = this.head!.val;
      this.head = this.head!.next;
    } else {
      let current = this.head;
      for (let i = 0; i < index - 1; i++) {
        current = current!.next;
      }
      removedVal = current!.next!.val;
      current!.next = current!.next!.next;
    }
    this.size--;
    return removedVal;
  }
 
  // Search - O(n)
  search(val: T): number {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.val === val) return index;
      current = current.next;
      index++;
    }
    return -1; // Not found
  }
 
  // Get value at index - O(n)
  get(index: number): T {
    if (index < 0 || index >= this.size) {
      throw new Error("Index out of bounds");
    }
    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current!.next;
    }
    return current!.val;
  }
 
  // Print list
  print(): string {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.val);
      current = current.next;
    }
    return values.join(" -> ") + " -> null";
  }
}
 
// Usage
const list = new SinglyLinkedList<number>();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);
console.log(list.print());  // 5 -> 10 -> 20 -> 30 -> null
list.insertAt(15, 2);
console.log(list.print());  // 5 -> 10 -> 15 -> 20 -> 30 -> null
list.delete(15);
console.log(list.print());  // 5 -> 10 -> 20 -> 30 -> null

# Python - Singly Linked List
class SinglyLinkedList:
    def __init__(self):
        self.head = None
        self.size = 0
 
    # Insert at the beginning - O(1)
    def prepend(self, val):
        new_node = ListNode(val, self.head)
        self.head = new_node
        self.size += 1
 
    # Insert at the end - O(n)
    def append(self, val):
        new_node = ListNode(val)
 
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node
        self.size += 1
 
    # Insert at specific position - O(n)
    def insert_at(self, val, index):
        if index < 0 or index > self.size:
            raise IndexError("Index out of bounds")
        if index == 0:
            self.prepend(val)
            return
 
        new_node = ListNode(val)
        current = self.head
        for _ in range(index - 1):
            current = current.next
        new_node.next = current.next
        current.next = new_node
        self.size += 1
 
    # Delete by value - O(n)
    def delete(self, val):
        if not self.head:
            return False
 
        if self.head.val == val:
            self.head = self.head.next
            self.size -= 1
            return True
 
        current = self.head
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
                self.size -= 1
                return True
            current = current.next
        return False
 
    # Search - O(n)
    def search(self, val):
        current = self.head
        index = 0
        while current:
            if current.val == val:
                return index
            current = current.next
            index += 1
        return -1
 
    # Print list
    def print_list(self):
        values = []
        current = self.head
        while current:
            values.append(str(current.val))
            current = current.next
        return " -> ".join(values) + " -> None"
 
 
# Usage
lst = SinglyLinkedList()
lst.append(10)
lst.append(20)
lst.append(30)
lst.prepend(5)
print(lst.print_list())  # 5 -> 10 -> 20 -> 30 -> None
lst.insert_at(15, 2)
print(lst.print_list())  # 5 -> 10 -> 15 -> 20 -> 30 -> None
lst.delete(15)
print(lst.print_list())  # 5 -> 10 -> 20 -> 30 -> None

Visualizing Insert & Delete

Insert at beginning (prepend):

Before:

After prepend(5):

Delete node with value 20:

Before:

After delete(20):

3. Doubly Linked List

Each node has pointers to both the next and previous nodes, enabling bidirectional traversal.

Node Structure

// TypeScript - Doubly Linked List Node
class DoublyNode<T> {
  val: T;
  next: DoublyNode<T> | null;
  prev: DoublyNode<T> | null;
 
  constructor(val: T) {
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}

# Python - Doubly Linked List Node
class DoublyNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None
        self.prev = None

Full Implementation

// TypeScript - Doubly Linked List
class DoublyLinkedList<T> {
  head: DoublyNode<T> | null = null;
  tail: DoublyNode<T> | null = null;
  size: number = 0;
 
  // Insert at beginning - O(1)
  prepend(val: T): void {
    const newNode = new DoublyNode(val);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }
    this.size++;
  }
 
  // Insert at end - O(1) with tail pointer!
  append(val: T): void {
    const newNode = new DoublyNode(val);
    if (!this.tail) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }
 
  // Delete node - O(1) when you have the node reference
  deleteNode(node: DoublyNode<T>): void {
    if (node.prev) {
      node.prev.next = node.next;
    } else {
      this.head = node.next; // Deleting head
    }
 
    if (node.next) {
      node.next.prev = node.prev;
    } else {
      this.tail = node.prev; // Deleting tail
    }
    this.size--;
  }
 
  // Delete from beginning - O(1)
  deleteFirst(): T | null {
    if (!this.head) return null;
    const val = this.head.val;
    this.deleteNode(this.head);
    return val;
  }
 
  // Delete from end - O(1) with tail pointer!
  deleteLast(): T | null {
    if (!this.tail) return null;
    const val = this.tail.val;
    this.deleteNode(this.tail);
    return val;
  }
 
  // Print forward
  printForward(): string {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.val);
      current = current.next;
    }
    return "null <-> " + values.join(" <-> ") + " <-> null";
  }
 
  // Print backward
  printBackward(): string {
    const values: T[] = [];
    let current = this.tail;
    while (current) {
      values.push(current.val);
      current = current.prev;
    }
    return "null <-> " + values.join(" <-> ") + " <-> null";
  }
}
 
// Usage
const dll = new DoublyLinkedList<number>();
dll.append(10);
dll.append(20);
dll.append(30);
dll.prepend(5);
console.log(dll.printForward());   // null <-> 5 <-> 10 <-> 20 <-> 30 <-> null
console.log(dll.printBackward());  // null <-> 30 <-> 20 <-> 10 <-> 5 <-> null
dll.deleteLast();
console.log(dll.printForward());   // null <-> 5 <-> 10 <-> 20 <-> null

# Python - Doubly Linked List
class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
 
    def prepend(self, val):
        new_node = DoublyNode(val)
        if not self.head:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
        self.size += 1
 
    def append(self, val):
        new_node = DoublyNode(val)
        if not self.tail:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
 
    def delete_node(self, node):
        if node.prev:
            node.prev.next = node.next
        else:
            self.head = node.next
 
        if node.next:
            node.next.prev = node.prev
        else:
            self.tail = node.prev
        self.size -= 1
 
    def delete_first(self):
        if not self.head:
            return None
        val = self.head.val
        self.delete_node(self.head)
        return val
 
    def delete_last(self):
        if not self.tail:
            return None
        val = self.tail.val
        self.delete_node(self.tail)
        return val
 
    def print_forward(self):
        values = []
        current = self.head
        while current:
            values.append(str(current.val))
            current = current.next
        return "None <-> " + " <-> ".join(values) + " <-> None"
 
 
# Usage
dll = DoublyLinkedList()
dll.append(10)
dll.append(20)
dll.append(30)
dll.prepend(5)
print(dll.print_forward())  # None <-> 5 <-> 10 <-> 20 <-> 30 <-> None
dll.delete_last()
print(dll.print_forward())  # None <-> 5 <-> 10 <-> 20 <-> None

Singly vs Doubly Linked List

Feature	Singly	Doubly
Memory per node	Data + 1 pointer	Data + 2 pointers
Traverse forward	Yes	Yes
Traverse backward	No	Yes
Delete with node ref	O(n)*	O(1)
Insert before node	O(n)*	O(1)
Append (with tail)	O(1)	O(1)
Delete last (with tail)	O(n)†	O(1)
Complexity	Simpler	More complex

*Need to find previous node | †Need to traverse to find second-to-last

4. Circular Linked List

In a circular linked list, the last node points back to the first node instead of null, forming a cycle.

Singly Circular:

Doubly Circular:

When to Use Circular Lists

Round-robin scheduling — cycling through tasks/players
Music playlists — loop back to the first song
Buffer management — circular buffers
Josephus problem — classic interview problem

// TypeScript - Simple Circular Linked List check
function isCircular<T>(head: ListNode<T> | null): boolean {
  if (!head) return false;
 
  let current = head.next;
  while (current && current !== head) {
    current = current.next;
  }
  return current === head;
}

# Python - Simple Circular Linked List check
def is_circular(head):
    if not head:
        return False
 
    current = head.next
    while current and current != head:
        current = current.next
    return current == head

5. The Dummy Head Technique

Many linked list problems require special handling for the head node. The dummy head (sentinel node) technique eliminates edge cases by adding a fake node before the real head.

// Without dummy head - must handle head separately
function deleteValue<T>(head: ListNode<T> | null, val: T): ListNode<T> | null {
  // Special case: head holds the value
  while (head && head.val === val) {
    head = head.next;
  }
 
  let current = head;
  while (current && current.next) {
    if (current.next.val === val) {
      current.next = current.next.next;
    } else {
      current = current.next;
    }
  }
  return head;
}
 
// With dummy head - clean, uniform logic
function deleteValueClean<T>(head: ListNode<T> | null, val: T): ListNode<T> | null {
  const dummy = new ListNode(0 as T, head); // Dummy node before head
  let current = dummy;
 
  while (current.next) {
    if (current.next.val === val) {
      current.next = current.next.next;
    } else {
      current = current.next;
    }
  }
  return dummy.next; // Real head
}

# Python - Dummy head technique
def delete_value_clean(head, val):
    dummy = ListNode(0, head)
    current = dummy
 
    while current.next:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next
 
    return dummy.next

Interview tip: Use a dummy head whenever the head of the list might change (deletions, insertions at the beginning, merging). It simplifies your code and reduces bugs.

6. Reversing a Linked List

Reversing a linked list is one of the most frequently asked interview questions. There are two approaches: iterative and recursive.

Iterative Approach (Recommended)

Use three pointers: prev, current, and next.

Step 1 — Reverse first pointer:

Step 2 — Continue reversing:

Done — All pointers reversed:

// TypeScript - Reverse Linked List (Iterative)
function reverseList(head: ListNode<number> | null): ListNode<number> | null {
  let prev: ListNode<number> | null = null;
  let current = head;
 
  while (current) {
    const next = current.next;  // Save next
    current.next = prev;        // Reverse pointer
    prev = current;             // Advance prev
    current = next;             // Advance current
  }
 
  return prev; // New head
}
 
// Time: O(n) | Space: O(1)

# Python - Reverse Linked List (Iterative)
def reverse_list(head):
    prev = None
    current = head
 
    while current:
        next_node = current.next  # Save next
        current.next = prev       # Reverse pointer
        prev = current            # Advance prev
        current = next_node       # Advance current
 
    return prev  # New head
 
# Time: O(n) | Space: O(1)

Recursive Approach

// TypeScript - Reverse Linked List (Recursive)
function reverseListRecursive(head: ListNode<number> | null): ListNode<number> | null {
  // Base case: empty list or single node
  if (!head || !head.next) {
    return head;
  }
 
  // Recursively reverse the rest
  const newHead = reverseListRecursive(head.next);
 
  // Reverse the pointer
  head.next.next = head;  // The node after head points back to head
  head.next = null;       // Head now points to null
 
  return newHead;
}
 
// Time: O(n) | Space: O(n) due to call stack

# Python - Reverse Linked List (Recursive)
def reverse_list_recursive(head):
    # Base case
    if not head or not head.next:
        return head
 
    # Recursively reverse the rest
    new_head = reverse_list_recursive(head.next)
 
    # Reverse the pointer
    head.next.next = head
    head.next = None
 
    return new_head
 
# Time: O(n) | Space: O(n) due to call stack

Interview tip: Interviewers often ask for both approaches. Start with iterative (O(1) space), then show recursive to demonstrate recursion skills.

7. Fast & Slow Pointers (Floyd's Algorithm)

The fast and slow pointer technique (also called Floyd's Tortoise and Hare) uses two pointers that traverse the list at different speeds. This pattern solves several linked list problems elegantly.

Detect Cycle in Linked List

Idea: If there's a cycle, the fast pointer (2 steps) will eventually catch up to the slow pointer (1 step).

// TypeScript - Detect Cycle (LeetCode 141)
function hasCycle(head: ListNode<number> | null): boolean {
  let slow = head;
  let fast = head;
 
  while (fast && fast.next) {
    slow = slow!.next;        // 1 step
    fast = fast.next.next;    // 2 steps
 
    if (slow === fast) {
      return true; // Cycle detected
    }
  }
 
  return false; // No cycle (fast reached end)
}
 
// Time: O(n) | Space: O(1)

# Python - Detect Cycle (LeetCode 141)
def has_cycle(head):
    slow = head
    fast = head
 
    while fast and fast.next:
        slow = slow.next       # 1 step
        fast = fast.next.next  # 2 steps
 
        if slow == fast:
            return True  # Cycle detected
 
    return False  # No cycle
 
# Time: O(n) | Space: O(1)

Find Cycle Start (LeetCode 142)

After detecting a cycle, reset one pointer to head and move both at the same speed — they'll meet at the cycle start.

Why does this work? If the distance from head to cycle start is a, and the meeting point is b steps into the cycle of length c, then:

Slow traveled: a + b
Fast traveled: a + b + c (went around the cycle once)
Since fast = 2 × slow: a + b + c = 2(a + b) → c = a + b → a = c - b

So starting from head and from the meeting point, both pointers need a steps to reach the cycle start.

// TypeScript - Find Cycle Start (LeetCode 142)
function detectCycle(head: ListNode<number> | null): ListNode<number> | null {
  let slow = head;
  let fast = head;
 
  // Step 1: Detect cycle
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
 
    if (slow === fast) {
      // Step 2: Find cycle start
      let pointer = head;
      while (pointer !== slow) {
        pointer = pointer!.next;
        slow = slow!.next;
      }
      return pointer; // Cycle start
    }
  }
 
  return null; // No cycle
}

# Python - Find Cycle Start (LeetCode 142)
def detect_cycle(head):
    slow = head
    fast = head
 
    # Step 1: Detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
        if slow == fast:
            # Step 2: Find cycle start
            pointer = head
            while pointer != slow:
                pointer = pointer.next
                slow = slow.next
            return pointer  # Cycle start
 
    return None  # No cycle

Find Middle of Linked List (LeetCode 876)

When slow reaches the middle, fast has reached the end.

// TypeScript - Find Middle Node
function middleNode(head: ListNode<number> | null): ListNode<number> | null {
  let slow = head;
  let fast = head;
 
  while (fast && fast.next) {
    slow = slow!.next;      // 1 step
    fast = fast.next.next;  // 2 steps
  }
 
  return slow; // Middle node
}
 
// For [1, 2, 3, 4, 5] → returns node 3
// For [1, 2, 3, 4, 5, 6] → returns node 4 (second middle)

# Python - Find Middle Node
def middle_node(head):
    slow = head
    fast = head
 
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    return slow
 
# Time: O(n) | Space: O(1)

8. Classic Interview Problems

Problem 1: Merge Two Sorted Lists (LeetCode 21)

Given two sorted linked lists, merge them into one sorted list.

// TypeScript - Merge Two Sorted Lists
function mergeTwoLists(
  l1: ListNode<number> | null,
  l2: ListNode<number> | null
): ListNode<number> | null {
  const dummy = new ListNode(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;
  }
 
  // Attach remaining nodes
  current.next = l1 || l2;
 
  return dummy.next;
}
 
// Time: O(n + m) | Space: O(1) — reusing existing nodes

# Python - Merge Two Sorted Lists
def merge_two_lists(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
 
    # Attach remaining nodes
    current.next = l1 if l1 else l2
 
    return dummy.next
 
# Time: O(n + m) | Space: O(1)

Problem 2: Remove Nth Node From End (LeetCode 19)

Remove the nth node from the end of the list in one pass.

Trick: Use two pointers separated by n nodes. When the fast pointer reaches the end, the slow pointer is right before the target.

// TypeScript - Remove Nth Node From End
function removeNthFromEnd(
  head: ListNode<number> | null,
  n: number
): ListNode<number> | null {
  const dummy = new ListNode(0, head);
  let fast: ListNode<number> | null = dummy;
  let slow: ListNode<number> | null = dummy;
 
  // Move fast pointer n+1 steps ahead
  for (let i = 0; i <= n; i++) {
    fast = fast!.next;
  }
 
  // Move both until fast reaches end
  while (fast) {
    fast = fast.next;
    slow = slow!.next;
  }
 
  // Skip the target node
  slow!.next = slow!.next!.next;
 
  return dummy.next;
}
 
// Time: O(n) | Space: O(1)

# Python - Remove Nth Node From End
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy
 
    # Move fast pointer n+1 steps ahead
    for _ in range(n + 1):
        fast = fast.next
 
    # Move both until fast reaches end
    while fast:
        fast = fast.next
        slow = slow.next
 
    # Skip the target node
    slow.next = slow.next.next
 
    return dummy.next
 
# Time: O(n) | Space: O(1)

Problem 3: Palindrome Linked List (LeetCode 234)

Check if a linked list is a palindrome using O(1) space.

Strategy:

Find the middle (fast & slow pointers)
Reverse the second half
Compare both halves

// TypeScript - Palindrome Linked List
function isPalindrome(head: ListNode<number> | null): boolean {
  if (!head || !head.next) return true;
 
  // Step 1: Find middle
  let slow: ListNode<number> | null = head;
  let fast: ListNode<number> | null = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
 
  // Step 2: Reverse second half
  let prev: ListNode<number> | null = null;
  let current = slow;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
 
  // Step 3: Compare both halves
  let left: ListNode<number> | null = head;
  let right: ListNode<number> | null = prev;
  while (right) {
    if (left!.val !== right.val) return false;
    left = left!.next;
    right = right.next;
  }
 
  return true;
}
 
// Time: O(n) | Space: O(1)

# Python - Palindrome Linked List
def is_palindrome(head):
    if not head or not head.next:
        return True
 
    # Step 1: Find middle
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    # Step 2: Reverse second half
    prev = None
    current = slow
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
 
    # Step 3: Compare both halves
    left = head
    right = prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
 
    return True
 
# Time: O(n) | Space: O(1)

Problem 4: Intersection of Two Linked Lists (LeetCode 160)

Find the node where two singly linked lists intersect.

Trick: If list A has length a and list B has length b, traverse both. When one reaches the end, redirect to the other list's head. They'll meet at the intersection after a + b steps.

// TypeScript - Intersection of Two Linked Lists
function getIntersectionNode(
  headA: ListNode<number> | null,
  headB: ListNode<number> | null
): ListNode<number> | null {
  let pA = headA;
  let pB = headB;
 
  while (pA !== pB) {
    pA = pA ? pA.next : headB;
    pB = pB ? pB.next : headA;
  }
 
  return pA; // Either intersection node or null
}
 
// Time: O(n + m) | Space: O(1)

# Python - Intersection of Two Linked Lists
def get_intersection_node(head_a, head_b):
    p_a = head_a
    p_b = head_b
 
    while p_a != p_b:
        p_a = p_a.next if p_a else head_b
        p_b = p_b.next if p_b else head_a
 
    return p_a  # Either intersection node or None
 
# Time: O(n + m) | Space: O(1)

Problem 5: Reorder List (LeetCode 143)

Reorder a list from L0 → L1 → ... → Ln to L0 → Ln → L1 → Ln-1 → ...

This problem combines three techniques: find middle, reverse, and merge.

// TypeScript - Reorder List
function reorderList(head: ListNode<number> | null): void {
  if (!head || !head.next) return;
 
  // Step 1: Find middle
  let slow: ListNode<number> | null = head;
  let fast: ListNode<number> | null = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
 
  // Step 2: Reverse second half
  let prev: ListNode<number> | null = null;
  let current = slow!.next;
  slow!.next = null; // Split the list
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
 
  // Step 3: Merge two halves alternately
  let first: ListNode<number> | null = head;
  let second: ListNode<number> | null = prev;
  while (second) {
    const tmp1 = first!.next;
    const tmp2 = second.next;
    first!.next = second;
    second.next = tmp1;
    first = tmp1;
    second = tmp2;
  }
}
 
// Time: O(n) | Space: O(1)

# Python - Reorder List
def reorder_list(head):
    if not head or not head.next:
        return
 
    # Step 1: Find middle
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    # Step 2: Reverse second half
    prev = None
    current = slow.next
    slow.next = None  # Split the list
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
 
    # Step 3: Merge two halves alternately
    first = head
    second = prev
    while second:
        tmp1 = first.next
        tmp2 = second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2
 
# Time: O(n) | Space: O(1)

9. Common Edge Cases

Edge cases are where most linked list bugs hide. Always test your solution with these:

Edge Case	Example	Why It Matters
Empty list	`head = null`	Null pointer exception
Single node	`[1] -> null`	No next node to process
Two nodes	`[1] -> [2] -> null`	Minimum for most operations
Duplicate values	`[1] -> 1 -> 2]`	Ensure all occurrences handled
Target at head	Delete head node	Must update head pointer
Target at tail	Delete last node	Must find previous node
All same values	`[5] -> [5] -> [5]`	Mass deletion edge case

// TypeScript - Always check these edge cases
function safeOperation(head: ListNode<number> | null): ListNode<number> | null {
  // Edge case 1: Empty list
  if (!head) return null;
 
  // Edge case 2: Single node
  if (!head.next) return head;
 
  // Edge case 3: Two nodes (common edge case for reversing, etc.)
  // ... your logic here
 
  return head;
}

10. Linked Lists in Real-World Applications

Linked lists aren't just interview fodder — they power critical systems:

Browser History (Doubly Linked List)

// Simplified browser history using doubly linked list
class BrowserHistory {
  private current: DoublyNode<string>;
 
  constructor(homepage: string) {
    this.current = new DoublyNode(homepage);
  }
 
  visit(url: string): void {
    const newPage = new DoublyNode(url);
    this.current.next = newPage;
    newPage.prev = this.current;
    this.current = newPage;
  }
 
  back(steps: number): string {
    while (steps > 0 && this.current.prev) {
      this.current = this.current.prev;
      steps--;
    }
    return this.current.val;
  }
 
  forward(steps: number): string {
    while (steps > 0 && this.current.next) {
      this.current = this.current.next;
      steps--;
    }
    return this.current.val;
  }
}

LRU Cache (Hash Map + Doubly Linked List)

The Least Recently Used (LRU) Cache is a classic system design problem that combines a doubly linked list with a hash map for O(1) operations.

# Python - LRU Cache (LeetCode 146)
class LRUNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None
 
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> node
 
        # Dummy head and tail
        self.head = LRUNode()
        self.tail = LRUNode()
        self.head.next = self.tail
        self.tail.prev = self.head
 
    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
 
    def _add_to_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
 
    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._remove(node)
            self._add_to_front(node)
            return node.val
        return -1
 
    def put(self, key, value):
        if key in self.cache:
            self._remove(self.cache[key])
 
        node = LRUNode(key, value)
        self._add_to_front(node)
        self.cache[key] = node
 
        if len(self.cache) > self.capacity:
            # Remove least recently used (from tail)
            lru = self.tail.prev
            self._remove(lru)
            del self.cache[lru.key]
 
# Usage
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1))    # 1
cache.put(3, 3)        # Evicts key 2
print(cache.get(2))    # -1 (not found)

Other Real-World Uses

Music player playlists — circular linked list for repeat mode
Undo/Redo systems — doubly linked list of states
Memory allocation — free lists in operating systems
Blockchain — each block points to the previous block
Hash table chaining — collision handling with linked lists
Operating system task scheduler — circular linked list

Summary and Key Takeaways

Core Concepts

Singly linked list: nodes with data + next pointer — simple, forward-only
Doubly linked list: nodes with prev + next — bidirectional, O(1) delete with node reference
Circular linked list: last node connects back to first — useful for cyclic processes

Essential Techniques

Technique	Use When	Key Idea
Dummy head	Head might change	Add fake node before head
Fast & slow pointers	Cycle detection, find middle	Two speeds reveal structure
Reverse linked list	Many problems need it	Use prev, current, next pointers
Two-pointer gap	Nth from end	Maintain fixed gap between pointers
Merge two lists	Combining sorted data	Use dummy head, compare values

Complexity Summary

Operation	Singly	Doubly
Access (by index)	O(n)	O(n)
Prepend	O(1)	O(1)
Append (with tail)	O(1)	O(1)
Insert at position	O(n)	O(n)*
Delete head	O(1)	O(1)
Delete tail	O(n)	O(1)
Search	O(n)	O(n)

*O(1) if you already have the previous node reference

Pattern Recognition

If you see...	Consider...
Cycle detection	Fast & slow pointers
Find middle	Fast & slow pointers
Merge sorted lists	Dummy head + compare
Reverse list	Three-pointer iterative
Nth from end	Two-pointer gap
Palindrome check	Find middle + reverse + compare
Reorder/rearrange	Find middle + reverse + merge
Head might change	Dummy head

Practice Problems

Easy

Medium

Hard

What's Next?

Now that you've mastered linked lists, you're ready to learn about Stacks and Queues in the next post. You'll discover:

LIFO (Stack) and FIFO (Queue) principles
Implementing stacks and queues from scratch
Classic problems: valid parentheses, next greater element
Real-world applications: function call stack, task scheduling

Continue your DSA journey: Stacks & Queues Complete Guide

Additional Resources

Previous Posts in This Series

DSA Roadmap - Complete learning path
Big O Notation & Complexity Analysis - Understanding time and space complexity
Problem-Solving Patterns & Techniques - Essential patterns for coding interviews
Arrays & Strings Complete Guide - Foundation data structures

Introduction

What You'll Learn

Prerequisites

1. What is a Linked List?

Arrays vs Linked Lists

Key Trade-offs

2. Singly Linked List

Node Structure

Full Implementation

Visualizing Insert & Delete

3. Doubly Linked List

Node Structure

Full Implementation

Singly vs Doubly Linked List

4. Circular Linked List

When to Use Circular Lists

5. The Dummy Head Technique

6. Reversing a Linked List

Iterative Approach (Recommended)

Recursive Approach

7. Fast & Slow Pointers (Floyd's Algorithm)

Detect Cycle in Linked List

Find Cycle Start (LeetCode 142)

Find Middle of Linked List (LeetCode 876)

8. Classic Interview Problems

Problem 1: Merge Two Sorted Lists (LeetCode 21)

Problem 2: Remove Nth Node From End (LeetCode 19)

Problem 3: Palindrome Linked List (LeetCode 234)

Problem 4: Intersection of Two Linked Lists (LeetCode 160)

Problem 5: Reorder List (LeetCode 143)

9. Common Edge Cases

10. Linked Lists in Real-World Applications

Browser History (Doubly Linked List)

LRU Cache (Hash Map + Doubly Linked List)

Other Real-World Uses

Summary and Key Takeaways

Core Concepts

Essential Techniques

Complexity Summary

Pattern Recognition

Practice Problems

Easy

Medium

Hard

What's Next?

Additional Resources

Previous Posts in This Series

📬 Subscribe to Newsletter

💬 Comments