0x70Lesson 8 of 13

Rewire linked lists

Reverse, merge, and detect cycles by moving node pointers carefully.

20 min 5-question quiz 1 code exercise

By the end of this lesson you can

Reverse a linked list iteratively.
Use fast and slow pointers to find the middle or detect a cycle.
Simplify edge cases with a dummy head node.

A linked list is a chain of nodes, each holding a value and a reference to the next node. Inserting or removing a node you already hold is O(1), but reaching the k-th node takes O(k). Linked-list questions test whether you can manipulate references without losing part of the list - so draw the boxes and arrows as you go.

Core techniques

Iterative reversal: walk the list with prev, current, and a saved next, pointing each node back at prev.
Fast and slow pointers: move one pointer two steps and the other one step. When fast reaches the end, slow is at the middle. If fast ever meets slow, the list has a cycle (Floyd’s algorithm).
Dummy head: start a result list with a placeholder node so inserting at the front needs no special case; return dummy.next.

solution.py

1class Node:
2    def __init__(self, value, next=None):
3        self.value = value
4        self.next = next
5
6def reverse(head):
7    prev = None
8    current = head
9    while current:
10        next_node = current.next  # save before rewiring
11        current.next = prev
12        prev = current
13        current = next_node
14    return prev
15
16head = Node(1, Node(2, Node(3)))
17node = reverse(head)
18while node:
19    print(node.value, end=" ")
20    node = node.next
21print()

Output

3 2 1

The order of the four assignments inside the loop matters: save current.next first, or the rest of the list is lost the moment you rewire current. Reversal is O(n) time and O(1) extra space. A recursive version is shorter but uses O(n) stack space.

Key takeaways

Save next before rewiring a node.
Fast/slow pointers find the middle and detect cycles in O(1) space.
A dummy head removes special cases when building lists.

Lesson quiz

5 questions · pass with 4 correct · up to 50 XP

Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.

Practice: solve interview problems

Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.

Exercise 1

Reverse a linked list

+25 XP

The starter code builds a linked list from a line of values. Reverse it by rewiring the nodes (not by reversing the Python list), then print the values from the new head, separated by spaces.

Five nodes
Single node

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Questions about this lesson

Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.

Loading posts…