Linked List Templates
A lot of the linked list solutions will depend on two things:
- finding the mid point
- reversing the linked list
It is useful to have these two methods handy.
Finding midpoint via slow and fast pointers (hare and tortoise)
def find_midpoint(head): slow,fast = head,head while fast is not None and fast.next is not None: slow = slow.next fast = fast.next.next return slow
Reversing linked list
Often times you will see things like finding the mid point first, and then reverse the second halve (e.g. testing whether linked list is a palindrome).
def reverse_linkedlist(head): prev = None while head is not None: temp = head.next head.next = prev prev = head head = temp return head