Intermediate

Linked Lists

Linked lists test pointer manipulation skills — a fundamental concept for understanding memory management, graph structures, and how Python objects reference each other. This lesson covers 5 classic problems.

ListNode Definition

All problems in this lesson use this standard node class:

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

# Helper: build linked list from array
def build_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    current = head
    for val in arr[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

# Helper: convert linked list to array for printing
def to_array(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

Problem 1: Reverse Linked List

Brute Force (Using Array): O(n) Time, O(n) Space

def reverse_list_brute(head):
    """Store values in array, rebuild list in reverse."""
    values = []
    current = head
    while current:
        values.append(current.val)
        current = current.next

    current = head
    for val in reversed(values):
        current.val = val
        current = current.next

    return head

# Test
head = build_list([1, 2, 3, 4, 5])
print(to_array(reverse_list_brute(head)))  # [5, 4, 3, 2, 1]

Optimal (Iterative): O(n) Time, O(1) Space

def reverse_list(head):
    """
    Reverse pointers one by one.

    Before: 1 -> 2 -> 3 -> 4 -> 5 -> None
    After:  None <- 1 <- 2 <- 3 <- 4 <- 5

    We maintain three pointers:
    - prev: the reversed portion (starts as None)
    - curr: current node being processed
    - next_node: saved reference to next node (before we break the link)
    """
    prev = None
    curr = head

    while curr:
        next_node = curr.next   # Save next
        curr.next = prev        # Reverse pointer
        prev = curr             # Move prev forward
        curr = next_node        # Move curr forward

    return prev  # prev is now the new head

# Test
head = build_list([1, 2, 3, 4, 5])
print(to_array(reverse_list(head)))  # [5, 4, 3, 2, 1]

head = build_list([1, 2])
print(to_array(reverse_list(head)))  # [2, 1]

head = build_list([])
print(to_array(reverse_list(head)))  # []

Recursive Approach: O(n) Time, O(n) Space (call stack)

def reverse_list_recursive(head):
    """
    Base case: empty list or single node.
    Recursive case: reverse the rest, then point next node back to current.
    """
    if not head or not head.next:
        return head

    new_head = reverse_list_recursive(head.next)
    head.next.next = head  # Point next node back to current
    head.next = None       # Remove forward pointer

    return new_head

# Test
head = build_list([1, 2, 3, 4, 5])
print(to_array(reverse_list_recursive(head)))  # [5, 4, 3, 2, 1]

AI/ML context: Reversing a linked list is analogous to backpropagation, where you reverse the forward computation to compute gradients. The iterative approach mirrors how frameworks traverse the computation graph backward.

Problem 2: Linked List Cycle

Brute Force (Hash Set): O(n) Time, O(n) Space

def has_cycle_brute(head):
    """Store visited nodes in a set."""
    visited = set()
    current = head
    while current:
        if id(current) in visited:
            return True
        visited.add(id(current))
        current = current.next
    return False

Optimal (Floyd's Tortoise and Hare): O(n) Time, O(1) Space

def has_cycle(head):
    """
    Floyd's cycle detection: use two pointers.
    - Slow pointer moves 1 step at a time
    - Fast pointer moves 2 steps at a time

    If there is a cycle, fast will eventually catch up to slow.
    If there is no cycle, fast will reach the end (None).

    Why it works: In a cycle, the distance between fast and slow
    decreases by 1 each step, so they must eventually meet.
    """
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True

    return False

# Test
# Create a cycle: 1 -> 2 -> 3 -> 4 -> 2 (cycle back to node 2)
head = build_list([1, 2, 3, 4])
head.next.next.next.next = head.next  # 4 -> 2

print(has_cycle(head))  # True

# No cycle
head2 = build_list([1, 2, 3])
print(has_cycle(head2))  # False

AI/ML context: Cycle detection is critical in computational graph validation. Before executing a DAG-based ML pipeline, you must verify there are no circular dependencies. Floyd's algorithm also appears in random number generator quality testing and detecting infinite loops in recursive model architectures.

Problem 3: Merge Two Sorted Lists

Optimal (Iterative): O(n + m) Time, O(1) Space

def merge_two_lists(list1, list2):
    """
    Use a dummy head to simplify edge cases.
    Compare nodes from both lists, append the smaller one.

    This is the merge step of merge sort applied to linked lists.
    """
    dummy = ListNode(0)
    current = dummy

    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next

    # Append remaining nodes (one list might not be exhausted)
    current.next = list1 if list1 else list2

    return dummy.next

# Test
l1 = build_list([1, 2, 4])
l2 = build_list([1, 3, 4])
print(to_array(merge_two_lists(l1, l2)))  # [1, 1, 2, 3, 4, 4]

l1 = build_list([])
l2 = build_list([0])
print(to_array(merge_two_lists(l1, l2)))  # [0]

Recursive Approach: O(n + m) Time, O(n + m) Space

def merge_two_lists_recursive(list1, list2):
    """Recursively pick the smaller head and merge the rest."""
    if not list1:
        return list2
    if not list2:
        return list1

    if list1.val <= list2.val:
        list1.next = merge_two_lists_recursive(list1.next, list2)
        return list1
    else:
        list2.next = merge_two_lists_recursive(list1, list2.next)
        return list2

AI/ML context: Merging sorted streams is essential in distributed training where multiple workers produce sorted gradient updates or sorted prediction results that need to be merged for aggregation.

Problem 4: Remove Nth Node From End of List

Brute Force (Two Pass): O(n) Time, O(1) Space

def remove_nth_from_end_brute(head, n):
    """First pass: count length. Second pass: remove node."""
    # Count length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Edge case: remove head
    if n == length:
        return head.next

    # Find node before target
    current = head
    for _ in range(length - n - 1):
        current = current.next

    current.next = current.next.next
    return head

Optimal (One Pass, Two Pointers): O(n) Time, O(1) Space

def remove_nth_from_end(head, n):
    """
    Use two pointers with a gap of n between them.

    1. Move 'fast' pointer n steps ahead
    2. Move both pointers until fast reaches the end
    3. 'slow' is now at the node before the target

    The dummy node handles the edge case of removing the head.
    """
    dummy = ListNode(0, head)
    slow = dummy
    fast = dummy

    # Move fast n+1 steps ahead
    for _ in range(n + 1):
        fast = fast.next

    # Move both until fast reaches end
    while fast:
        slow = slow.next
        fast = fast.next

    # Remove the nth node from end
    slow.next = slow.next.next

    return dummy.next

# Test
head = build_list([1, 2, 3, 4, 5])
print(to_array(remove_nth_from_end(head, 2)))  # [1, 2, 3, 5]

head = build_list([1])
print(to_array(remove_nth_from_end(head, 1)))  # []

head = build_list([1, 2])
print(to_array(remove_nth_from_end(head, 1)))  # [1]

AI/ML context: The two-pointer gap technique is used in sliding window computations over sequential data, which is common in time-series forecasting and sequence-to-sequence models. The concept of maintaining a fixed offset between pointers appears in attention mechanism implementations.

Problem 5: Intersection of Two Linked Lists

Brute Force (Hash Set): O(n + m) Time, O(n) Space

def get_intersection_brute(headA, headB):
    """Store all nodes from list A, then check list B."""
    nodes = set()
    current = headA
    while current:
        nodes.add(id(current))
        current = current.next

    current = headB
    while current:
        if id(current) in nodes:
            return current
        current = current.next

    return None

Optimal (Two Pointers): O(n + m) Time, O(1) Space

def get_intersection(headA, headB):
    """
    Elegant two-pointer approach:
    - Pointer A traverses list A, then switches to list B
    - Pointer B traverses list B, then switches to list A

    Both pointers travel the same total distance:
    len(A) + len(B) = len(B) + len(A)

    If lists intersect, pointers meet at the intersection.
    If not, both reach None at the same time.

    Why it works: The switch equalizes the "extra" distance
    before the intersection point.
    """
    if not headA or not headB:
        return None

    ptrA = headA
    ptrB = headB

    while ptrA != ptrB:
        ptrA = ptrA.next if ptrA else headB
        ptrB = ptrB.next if ptrB else headA

    return ptrA  # Either intersection node or None

# Test
# Create intersection: A: 1->2->8->4->5, B: 3->8->4->5
shared = build_list([8, 4, 5])
headA = ListNode(1, ListNode(2, shared))
headB = ListNode(3, shared)

result = get_intersection(headA, headB)
print(result.val if result else None)  # 8

# No intersection
headC = build_list([1, 2, 3])
headD = build_list([4, 5, 6])
result = get_intersection(headC, headD)
print(result)  # None

AI/ML context: Finding shared structures between different data representations is important in knowledge graph alignment, entity resolution across datasets, and detecting shared computation in model architectures for optimization.

Summary: Complexity Comparison

Problem	Brute Force	Optimal	Key Technique
Reverse List	O(n) / O(n) space	O(n) / O(1) space	Three-pointer reversal
Detect Cycle	O(n) / O(n) space	O(n) / O(1) space	Floyd's tortoise and hare
Merge Sorted	N/A	O(n + m) / O(1)	Dummy head + compare
Remove Nth End	O(n) two pass	O(n) one pass	Two pointers with gap
Intersection	O(n+m) / O(n)	O(n+m) / O(1)	Pointer switch technique