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.
Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.
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.
- The number of nodes in the list is in the range
1 <= Node.val <= 100
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
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.
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.next reaches the end, the
slow pointer will point to the middle node.
# 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
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