Find Half Of A Linked List

Given a linked list with the following ListNode

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

In order to find half of the list, we can do as following:

def findHalf(head: ListNode):
	if not head: raise Exception()
	
	slow, fast = head, head.next # slow will then be first item on the left

	while (fast and fast.next):
		slow = slow.next
		fast = fast.next.next

	print("Slow is now at half of the list (n // 2)")

Since fast going 2 nodes at a time. There could be a situation at the end where fast is null already to do fast.next.

Therefore we have the guard fast = fast.next

If n is:

• odd: Slow is the middle item
• even:
  • Slow is the last item on the left if we start with fast = head.next
  • Slow is the first item on the right if we start with fast = head

[!caution]
However fast could be either the last element or null. We're not sure