Common Questions

Find the middle of a linked list given the head node#

  • Use the runner technique. Have a slow pointer and a fast pointer. Slow pointer is always incremented by one (slow = slow.next), while fast pointer is increment twice (fast = fast.next.next).
  • When the fast pointer points to null, it has reached the end of the LL, but slow pointer will be pointing to the middle node.
  • Return that node.

Find if a linked list has any loops#

  • Runner technique (aka Floyd's cycle finding algorithm). Slow pointer and fast pointer. Slow increments by one, while fast increments twice. If the slow and fast pointer meet at any point in time, then we have found a loop. Else if, any pointer reaches the null node, we stop as there are no loops.

Find the node at the start of a loop#

  • In (2), we found if the linked list has a loop. That collision of the pointers could have happened anywhere within the loop. Sometimes it is useful to find where the loop starts.
  • Approach: Same as before, have a slow and fast pointer and advance the fast pointer twice as fast as slow pointer till they collide.
  • Now reset one of the pointers back to the start of the linked list, i.e. the head. Now advance both the slow and "fast" pointers by 1 step at the same time.
  • The point at which they meet will be the start of the loop.

Reverse a linked list#

# iterative
def reverse(self):
prev = None
curr = self.head
while(curr is not None):
next = curr.get_next()
curr.set_next(prev)
prev = curr
curr = next
self.head = prev
# recursive
def _recursive_reverse(self, node):
if(node.get_next() is None):
self.head = node
return node
else:
curr = self._recursive_reverse(node.get_next())
curr.set_next(node)
print(curr, node)
curr = node
curr.set_next(None)
return curr