DSA

Linked Lists

Interview Prep · 7 entries

Linked List Traversal

Syntax

class ListNode:
  val, next

Start at head, follow next pointers until null.

Example

// JavaScript
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function traverse(head) {
  const values = [];
  let current = head;
  while (current !== null) {
    values.push(current.val);
    current = current.next;
  }
  return values;
}

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

def traverse(head):
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next
    return values

Output

1 → 2 → 3 → None
traverse(head) → [1, 2, 3]

Note Time O(n), Space O(1) for traversal itself. The dummy/sentinel node trick simplifies edge cases: create a dummy node pointing to head, return dummy.next at the end. This avoids special-casing operations on the head node.

linked list traversaliterate linked listListNodesingly linked list

Reverse a Linked List

Syntax

Iterative: maintain prev, current, next pointers.
At each step: save next, point current.next to prev, advance both.

Example

// JavaScript - Iterative
function reverseList(head) {
  let prev = null, current = head;
  while (current !== null) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

// Recursive
function reverseListRecursive(head) {
  if (!head || !head.next) return head;
  const newHead = reverseListRecursive(head.next);
  head.next.next = head;
  head.next = null;
  return newHead;
}

# Python - Iterative
def reverse_list(head):
    prev, current = None, head
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    return prev

# Recursive
def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

Output

1→2→3→4 becomes 4→3→2→1

Note Iterative: O(n) time, O(1) space. Recursive: O(n) time, O(n) stack space. This is the single most common linked list question. Draw the pointer changes on paper. Follow-up: reverse a sublist from position m to n.

reverse linked listlist reversaliterative reverserecursive reverse

Detect Cycle (Floyd's Tortoise & Hare)

Syntax

Use slow (1 step) and fast (2 steps) pointers.
If they meet → cycle exists.
To find cycle start: reset one pointer to head, move both at 1 step.

Example

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

function findCycleStart(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      slow = head;
      while (slow !== fast) {
        slow = slow.next;
        fast = fast.next;
      }
      return slow; // cycle start node
    }
  }
  return null;
}

# Python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

def find_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow
    return None

Output

Has cycle: True/False
Cycle start: node where cycle begins

Note Time O(n), Space O(1). The math behind finding the cycle start: when they meet, the distance from head to cycle start equals the distance from meeting point to cycle start (going around). Always use 'is' (identity) not '==' (equality) for node comparison.

detect cycleFloyd's algorithmtortoise and hare cycle detectionlinked list cycle

Find Middle of Linked List

Syntax

Slow pointer moves 1 step, fast moves 2 steps.
When fast reaches end, slow is at the middle.

Example

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

# Python
def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Output

1→2→3→4→5 → middle is 3
1→2→3→4 → middle is 3 (second of two middles)

Note Time O(n), Space O(1). For even-length lists, this returns the second middle node. To get the first middle, use: while fast.next and fast.next.next. This technique is a building block for merge sort on linked lists and palindrome checking.

find middlemiddle nodeslow fast pointerlinked list middle

Merge Two Sorted Linked Lists

Syntax

Use a dummy node. Compare heads of both lists, attach the smaller one.
Advance the pointer of the list you took from.

Example

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

# Python
def merge_two_lists(l1, l2):
    dummy = ListNode(0)
    tail = dummy
    while l1 and 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 or l2
    return dummy.next

Output

1→3→5 + 2→4→6 → 1→2→3→4→5→6

Note Time O(n + m), Space O(1). The dummy node pattern eliminates edge cases for choosing the initial head. Follow-up: merge k sorted lists - use a min-heap for O(n log k) or divide and conquer.

merge sorted listsmerge two listsdummy nodesorted merge

Remove N-th Node from End

Syntax

Use two pointers with a gap of n between them.
Advance both until the lead pointer hits the end.
The trailing pointer is right before the target.

Example

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

# Python
def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    lead = trail = dummy
    for _ in range(n + 1):
        lead = lead.next
    while lead:
        lead = lead.next
        trail = trail.next
    trail.next = trail.next.next
    return dummy.next

Output

1→2→3→4→5, n=2 → 1→2→3→5 (removed 4)

Note Time O(n), Space O(1), single pass. The dummy node handles removing the head itself (when n equals list length). Always advance lead n+1 times so trail stops one node before the target.

remove nth from endtwo pointer gaplinked list removalsingle pass removal

Palindrome Check for Linked List

Syntax

1. Find the middle using slow/fast pointers
2. Reverse the second half
3. Compare first half with reversed second half
4. (Optional) Restore the list

Example

// JavaScript
function isPalindrome(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  // Reverse second half
  let prev = null;
  while (slow) {
    const next = slow.next;
    slow.next = prev;
    prev = slow;
    slow = next;
  }
  // Compare halves
  let left = head, right = prev;
  while (right) {
    if (left.val !== right.val) return false;
    left = left.next;
    right = right.next;
  }
  return true;
}

# Python
def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    prev = None
    while slow:
        slow.next, prev, slow = prev, slow, slow.next
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left, right = left.next, right.next
    return True

Output

1→2→3→2→1 → True
1→2→3→4 → False

Note Time O(n), Space O(1). Combines three linked list skills: find middle, reverse, and compare. An O(n) space alternative: copy values to an array and check palindrome there. Interviewers prefer the O(1) space approach.

palindrome linked listcheck palindromereverse halflinked list palindrome