5. Linked Lists

What Interviewers Test Here

• Pointer manipulation (reverse, splice, skip)
• Fast/slow pointer (Floyd's cycle detection, middle node, kth from end)
• Dummy head node to simplify edge cases

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

# --- Reverse ---
def reverse(head: ListNode | None) -> ListNode | None:
    prev, cur = None, head
    while cur:
        nxt      = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

# --- Detect cycle ---
def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# --- Find middle ---
def middle(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

# --- Remove Nth from end (one pass) ---
def remove_nth(head: ListNode, n: int) -> ListNode | None:
    dummy = ListNode(0, head)
    fast  = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    slow.next = slow.next.next
    return dummy.next

---

Conceptual Q&A

Q1: "How would you detect if a linked list has a cycle?"

Walkthrough:

"Brute force: store every visited node in a set. If I see the same node twice, there's a cycle. $O(n)$ time, $O(n)$ space.

Can I do it in $O(1)$ space? Yes — Floyd's Tortoise and Hare algorithm. Two pointers: slow moves 1 step, fast moves 2 steps. If there's no cycle, fast reaches the end. If there's a cycle, fast laps slow — they'll meet inside the cycle. $O(n)$ time, $O(1)$ space.

The interviewer might ask: why do they always meet? If the cycle length is $C$ and they enter the cycle at distance $k$ from the start, after entering they're moving at relative speed 1 toward each other within the cycle — they must meet within $C$ steps."

def has_cycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:   # they met — cycle exists
            return True
    return False

# Bonus: find the START of the cycle
def cycle_start(head: ListNode | None) -> ListNode | None:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Reset one pointer to head; both move at speed 1
            slow = head
            while slow is not fast:
                slow = slow.next
                fast = fast.next
            return slow   # meeting point = cycle start
    return None

---

Q2: "Given a linked list, determine if it is a palindrome."

Walkthrough:

"A palindrome reads the same forwards and backwards. For arrays I'd use two pointers — can I do the same here?

I can't directly index into a linked list. My approach:

1. Find the middle of the list (slow/fast pointers)
2. Reverse the second half
3. Compare the first half and reversed second half node by node
4. (Optionally restore the list)

$O(n)$ time, $O(1)$ space."

def is_palindrome(head: ListNode | None) -> bool:
    if not head or not head.next:
        return True
    # Step 1: Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # Step 2: Reverse second half
    prev, cur = None, slow
    while cur:
        nxt = cur.next; cur.next = prev; prev = cur; cur = nxt
    # Step 3: Compare
    left, right = head, prev
    while right:
        if left.val != right.val:
            return False
        left  = left.next
        right = right.next
    return True

---