Given the head
of a singly linked list, return the middle node of the linked list.
Constraints:
- The number of nodes in the list is in the range
[1, 100]
. $1 \leq Node.val \leq 100$
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.
Trivial case is a single node. We should just return the node.
Bottom line is we have to traverse all nodes before we know which one is the middle one. So time complexity has to be at least O(N)
.
Naively we can put all nodes in a list as we scan the linked list and get the middle node. That would cost O(N)
space.
However, we can use some math and only record the mid node mid_node
when our scanning pointer pos
position changes.
- Initialise
mid_node = head
,pos = 0
,curr_node = head
- while
curr_node.next is not None
curr_node = curr_node.next
pos += 1
- if
pos % 2 == 1
,mid_node = mid_node.next
def middleNode(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
mid_node = head
pos = 0
curr_node = head
while curr_node.next:
curr_node = curr_node.next
pos += 1
if pos % 2 == 1:
mid_node = mid_node.next
return mid_node
O(N)
O(1)
nil
.
<<imports for typing>>