Middle of a linked list
Given the head of a singly linked list, return its middle node in one pass. If there are two middle nodes, return the second.
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
# 1 -> 2 -> 3 -> 4 -> 5 middle is 3
# 1 -> 2 -> 3 -> 4 -> 5 -> 6 middle is 4Show hint
Move one pointer one step at a time and another two steps at a time.
Show solution
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowWhen the fast pointer reaches the end, the slow one has gone exactly half as far. One pass and O(1) space, without counting the length first. The same two-speed idea detects cycles.
Want a problem like this every day? See today's problem and keep a streak going.