Middle of the Linked List
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.
Example 1:
Input: head = [1, 2, 3, 4, 5]
Output: [3, 4, 5]
Explanation: The middle node of the list is node 3.
For a list with 5 nodes, the middle is at position 3 (1-indexed).
Example 2:
Input: head = [1, 2, 3, 4, 5, 6]
Output: [3, 4, 5, 6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one (node 4).
For a list with 6 nodes, positions 3 and 4 are middle. We return position 4.
Example 3:
Input: head = [1]
Output: [1]
Explanation: The only node is both the head and the middle.
Constraints
The number of nodes in the list is in the range [1, 100]1 <= Node.val <= 100
Complexity
Show Complexity
- Time:
O(n) - Space:
O(1)
Hints
Show Hints
- Pattern
- Two pointers (slow and fast)
- Approach
- Use two pointers: slow moves 1 step, fast moves 2 steps. When fast reaches the end, slow is at the middle.
- Complexity
- One pass with O(1) space using slow/fast pointers
Solutions
Show PY Solution
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def solution(head: ListNode) -> ListNode:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow