Practice Problems

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 3 Time to complete: ~30 minutes

Remove the Nth Node From the End
Palindrome Linked List
Intersection of Two Linked Lists
Try It Yourself
Summary & Next Steps

1. Remove the Nth Node From the End

Problem: Given a linked list, remove the node that is n positions from the end, in a single pass.

Approach: Use two pointers with a fixed gap of n nodes between them. When the front pointer reaches the end, the back pointer is exactly at the node before the one to remove.

def remove_nth_from_end(head, n):
    dummy = Node(None)          # handles the edge case of removing the head itself
    dummy.next = head
    fast = dummy
    slow = dummy
 
    for _ in range(n):           # open up a gap of n nodes
        fast = fast.next
 
    while fast.next is not None:
        fast = fast.next
        slow = slow.next
 
    slow.next = slow.next.next   # skip over the target node
    return dummy.next
    # O(n) time — one pass; O(1) space

This is the same two-pointer-with-a-gap idea used for "find the middle" in Chapter 3, adapted to keep a trailing reference instead of a centered one.

2. Palindrome Linked List

Problem: Determine whether a linked list reads the same forwards and backwards.

Approach: Find the middle (Chapter 3), reverse the second half (Chapter 3), then compare the two halves value-by-value.

def is_palindrome(head):
    if head is None or head.next is None:
        return True
 
    # Step 1: find the middle using fast/slow pointers
    slow, fast = head, head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
 
    # Step 2: reverse the second half
    second_half = reverse_iterative(slow)
 
    # Step 3: compare first half against reversed second half
    first_half = head
    while second_half is not None:      # second half is equal or shorter length
        if first_half.value != second_half.value:
            return False
        first_half = first_half.next
        second_half = second_half.next
 
    return True
    # O(n) time, O(1) auxiliary space — no array copy needed

The naive approach — copy all values into a Python list and check if it equals its reverse — also works and is simpler to write, but costs O(n) extra space for the copy. This in-place version keeps space at O(1) by reusing the list's own nodes, the same tradeoff theme from Module 1, Chapter 4.

3. Intersection of Two Linked Lists

Problem: Given two singly linked lists that may converge into a shared tail (like a "Y" shape), find the node where they intersect.

Approach: The naive approach checks every node of list A against every node of list B — O(n × m). A cleverer approach: walk both lists to their ends, switching to the other list's head once you run out — both pointers then travel the same total distance and arrive at the intersection together.

def get_intersection(head_a, head_b):
    pointer_a = head_a
    pointer_b = head_b
 
    while pointer_a is not pointer_b:
        pointer_a = pointer_a.next if pointer_a is not None else head_b
        pointer_b = pointer_b.next if pointer_b is not None else head_a
 
    return pointer_a         # either the intersection node, or None if no intersection
    # O(n + m) time, O(1) space

Why this works: if list A has length a before the intersection and list B has length b, then pointer_a travels a + (b - offset) total and pointer_b travels b + (a - offset) — both cover a + b total steps by the time they reach the intersection point (or both hit None at the same time if there's no intersection), so they're guaranteed to meet.

4. Try It Yourself

Before moving to Module 7, work through these using the patterns from this module:

# (a) Given the head of a linked list, remove all nodes with a given value.
#     Hint: the dummy-node trick from Chapter 3 handles removing the head cleanly.
 
# (b) Given the head of a linked list, reorder it so that
#     L0 → L1 → ... → Ln  becomes  L0 → Ln → L1 → Ln-1 → L2 → ...
#     Hint: find the middle, reverse the second half, then merge the two halves alternately.
 
# (c) Determine whether a linked list has a cycle, and if it does, return the node
#     where the cycle begins (not just whether one exists).
#     Hint: after the fast/slow pointers meet (Chapter 3), resetting one pointer to
#     the head and advancing both one step at a time will meet again at the cycle's start.

Hints expanded (click to expand)

(a) Iterate with a dummy.next = head setup; when current.next.value == target, skip it (current.next = current.next.next) instead of advancing current.
(b) This is exactly Chapter 3's "find middle" + "reverse" + a modified merge that alternates nodes from each half instead of comparing values.
(c) This extension of Floyd's algorithm relies on the same distance math as the intersection problem above — once pointers meet inside the cycle, the distance from the meeting point to the cycle's start equals the distance from the head to the cycle's start.

5. Summary & Next Steps

Key Takeaways

The two-pointer-with-a-gap technique (nth-from-end) and fast/slow pointers (palindrome, cycle detection) are the two workhorse patterns for linked list problems — most problems in this module reduce to one of them.
Reusing existing nodes instead of copying into a new array is what keeps these solutions at O(1) auxiliary space instead of O(n).
The intersection problem's "switch lists when you run out" trick is a clever O(1)-space alternative to the naive O(n × m) or a hash-set-based O(n + m) time / O(n) space approach.

Concept Check

Why does opening a gap of n nodes before starting the second pointer let you find "nth from the end" in one pass?
Why is the in-place palindrome check preferred over copying into a Python list, even though both are O(n) time?
Walk through why the two pointers in the intersection problem are guaranteed to meet at the correct node.

Next Module

→ Module 7: Trees & Heaps

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index