Finding the Middle of a Linked List (with Animated Examples)

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

The number of nodes in the list is in the range [1, 100]. 1 <= Node.val <= 100

Solution

Approach 1: Two Passes

1. Find the length of the linked list by traversing the list.
2. Find the middle node by traversing the list again to the middle.
3. Return the middle node

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def middle_node(head: ListNode) -> ListNode:
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    middle = length // 2
    current = head
    for _ in range(middle):
        current = current.next

    return current

Time complexity: O(n) Space complexity: O(1)

Approach 2: One Pass

1. Use two pointers, one fast and one slow.
2. Move the fast pointer two nodes at a time and the slow pointer one node at a time.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
def middle_node(head: ListNode) -> ListNode:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

Time complexity: O(n) Space complexity: O(1)