Reverse, Middle and Cycle Detection
30 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Three small tricks solve most linked list questions. Reverse the links with prev and node. Walk two pointers at different speeds to find the middle or a cycle. This lesson builds each one and then combines them.
Reverse a list
In-place reversal turns every next link around so the list runs the other way. It reuses the same nodes with a few variables, taking O(n) time and O(1) extra space.
To reverse a list, turn every link around. Keep prev, the part already reversed, and node, the one being turned. Save node.next first, or the rest of the list is lost.
def reverse(head): prev = None node = head while node: nxt = node.next node.next = prev prev = node node = nxt return prevExample 1 · Reverse and print before and after
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def reverse(head): prev = None node = head while node: nxt = node.next node.next = prev prev = node node = nxt return prev
head = build([1, 2, 3, 4])print(to_list(head))head = reverse(head)print(to_list(head))[1, 2, 3, 4] [4, 3, 2, 1]
What this code does
- The four nodes are the same objects before and after. Only their
nextlinks changed. - Always take the result: after reversing, the old head is the last node, so the old name no longer starts the list.
Example 2 · The same reversal with one tuple assignment
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
def reverse(head): prev = None while head: head.next, prev, head = prev, head, head.next return prev
print(to_list(reverse(build(["A", "B", "C"]))))['C', 'B', 'A']
What this code does
- The right side is read completely first, so the old
head.nextis saved before any link is changed. - This is a Python habit. In an interview the four-line version is easier to explain and to check.
When the loop ends, node is None and prev is the old last node, which is the new head. It reuses the nodes, so it is O(n) time and O(1) space.
Find the middle
To find the middle without counting first, move two pointers along the list. Slow takes one step and fast takes two. When fast runs out, slow is in the middle.
def middle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slowExample 3 · Brute force middle: copy to a list
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def to_list(head): out = [] node = head while node: out.append(node.value) node = node.next return out
head = build([10, 20, 30, 40, 50])values = to_list(head)print(values[len(values) // 2])30
What this code does
- Copy the values into a Python list and read the middle one. It is simple and O(n) in time.
- It needs O(n) extra space, which the two pointer version avoids.
Example 4 · Middle of an odd and an even list
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def middle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow
print(middle(build([1, 2, 3, 4, 5])).value)print(middle(build([1, 2, 3, 4, 5, 6])).value)3 4
What this code does
- With five nodes the middle is 3. With six nodes there are two middles, 3 and 4, and this version returns the second.
- To get the first middle, start
fastathead.next.
This is the fast and slow idea from the two pointers module. For an even length it returns the second of the two middle nodes. The test fast and fast.next keeps the two-step jump inside the list.
Detect a cycle
Cycle in a linked list means some node's next points back to an earlier node, so walking from the head never reaches None. Fast and slow pointers detect it in O(n) time and O(1) space.
A list can have a cycle if some node's next points back to an earlier node. Walking then never reaches None. Fast and slow pointers meet inside a cycle, and fast reaches None if there is none.
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 FalseExample 5 · Cycle detection: a set and two pointers
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def has_cycle_set(head): seen = set() node = head while node: if node in seen: return True seen.add(node) node = node.next return False
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
c = Node(3)head = Node(1, Node(2, c))print(has_cycle(head), has_cycle_set(head))c.next = head.nextprint(has_cycle(head), has_cycle_set(head))False False True True
What this code does
- First the list ends at 3, so both say False. Then the last node is linked back to the second node, which makes a cycle.
- The set stores every node, so it uses O(n) space. Two pointers use O(1).
Use is, not ==, because the question is whether both names point at the very same node. Time is O(n) and space is O(1). A set of visited nodes also works but costs O(n) space.
Find where the cycle starts
After the pointers meet, put one pointer back at the head. Move both one step at a time. They meet exactly at the first node of the cycle.
def 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 NoneExample 6 · Where a cycle starts and how long it is
class Node: def __init__(self, value, next=None): self.value = value self.next = next
nodes = [Node(v) for v in [5, 6, 7, 8, 9]]for a, b in zip(nodes, nodes[1:]): a.next = bnodes[-1].next = nodes[2]head = nodes[0]
slow = fast = headwhile fast and fast.next: slow = slow.next fast = fast.next.next if slow is fast: breaklength = 1node = slow.nextwhile node is not slow: node = node.next length += 1slow = headwhile slow is not fast: slow = slow.next fast = fast.nextprint(slow.value, length)7 3
What this code does
- The last node 9 links back to the node holding 7, so the cycle is 7, 8, 9 and has length 3.
- Walking once around from the meeting point counts the length. Resetting one pointer to the head finds the start.
Example 7 · Check a palindrome list with O(1) extra space
class Node: def __init__(self, value, next=None): self.value = value self.next = next
def build(values): head = None for value in reversed(values): head = Node(value, head) return head
def is_palindrome(head): slow = fast = head while fast and fast.next: slow, fast = slow.next, fast.next.next prev = None while slow: slow.next, prev, slow = prev, slow, slow.next left, right = head, prev while right: if left.value != right.value: return False left, right = left.next, right.next return True
print(is_palindrome(build([1, 2, 3, 2, 1])))print(is_palindrome(build([1, 2, 3, 4])))True False
What this code does
- Find the middle, reverse the second half, then compare both halves from the outside in.
- Copying the values to a list and comparing it with its reverse is simpler, but uses O(n) space. This version uses O(1) and changes the list.
The distance from the head to the cycle start equals the distance from the meeting point to the cycle start, going around. That is why walking both pointers at the same speed makes them meet there.
Next step
Check your understanding
12 quick questions