Middle Of The Linked List

---

Intuition

• This uses the fast pointer slow pointer approach.
• Even nodes:
  • say 10, then when fast is at 9 (1-indexed), it will go to fast.next.next, which is None.
  • At that point, there will be 5 iterations + 1 for the None
    • 1, 3, 5, 7, 9, 11 = 5 iterations
• Odd nodes:
  • Say 9, then when fast is at 9 (1-indexed), it won’t have a next, so the loop will end.
    • 1, 3, 5, 7, 9 = 5 iterations
• Either way, the slow pointer will end up in the right final position.

Complexity

Runtime

$O(N)$, where N is the number of nodes.

Space

$O(1)$

Code

Simplified

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

Original

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
		slow = fast = head
        while fast.next:
            slow = slow.next
            fast = fast.next
            if not fast.next:
                return slow
            fast = fast.next
 
        return slow

Notes

Cards

START Basic Front: Middle Of The Linked List Back: Use fast pointer slow pointer, noticing that the slow pointer will end up in the right position always.

END

---

References

• Middle Of The Linked List