Problem Statement

Description

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.

Examples

Example 1:

flowchart LR a((1))-->b((2))-->c(3)-->d((4))-->e((5))
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

flowchart LR a((1))-->b((2))-->c((3))-->d(4)-->e((5))-->f((6))
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

Key Insights

The most straight forward way to approach this problem is to find the number of nodes in the list and then return node n // 2 (zero-indexed). If we have 6 nodes in the linked list, we will get node 3. If we have 5 nodes, we will get node 2.

We are essentially returning the second half of the linked list. If the length of the list is even, we have two equal halves. If the length is odd, the second half is one node longer than the first half.

flowchart LR a((0))-->b((1))-->c((2))-->d(3)-->e((4))-->f((5))
flowchart LR a((0))-->b((1))-->c(2)-->d((3))-->e((4))

In the previous approach we found the middle node in two passes. Although this is linear time O(N), there is a better way. We can actually achieve one-pass linear time if we use two pointers. If the fast pointer advances two nodes for every one node the slow pointer moves, by the time fast or fast.next reaches the end, the slow pointer will point to the middle node.

Python Solution

Two Passes

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        n = 0
        curr = head

        # find the length of the linked list
        while curr:
            n += 1
            curr = curr.next

        curr = head

        # Traverse up to the middle node
        for i in range(n//2):
            curr = curr.next

        # Return the middle node
        return curr

Two Pointers

class Solution:
    def middle(self, head: "ListNode") -> "ListNode":
        """
            T: O(N)
            S: O(1)
        """
        # Initialize two pointers
        slow = head
        fast = head
        """
        Case 1: (even length)
            1-->2-->3-->4
                    ^slow
                            ^fast

        Case 2: (odd length)
            1-->2-->3-->4-->5
                    ^slow
                            ^fast
        """

        # Every time the slow pointer advances one,
        # the fast pointer advances two. If the list
        # has an even number of nodes, the fast pointer
        # will overshoot the end and the slow pointer 
        # will be the head of the second half of the list.
        # If the list has an odd number of nodes, the fast
        # pointer will end on the last node, and the slow
        # pointer will land on the middle node
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow