Find the Middle Node of a Linked List
In Uber's backend systems, linked lists might be used to represent sequences of events, trip segments, or even driver queues. Sometimes, it's necessary to quickly identify a central point in such a sequence, perhaps to split a task, balance load, or find a representative element. This problem focuses on efficiently locating the middle element of a given sequence represented as a singly linked list.
Implement a function middleNode that takes the head of a singly linked list and returns its middle node. If the list has an even number of nodes, return the second middle node.
head - The head node of a singly linked list. Each node has an integer val and a next pointer.head will always point to a valid ListNode or be null. However, for this problem, assume the list will always contain at least one node.[1, 2, 3, 4, 5, 6], the middle nodes are 3 and 4. You should return the node with value 4.Examples
Example 1
Input:
head = [1,2,3,4,5]
Output:
[3,4,5]
Note:
The list has 5 nodes. The middle node is the 3rd node, with value 3.
Example 2
Input:
head = [1,2,3,4,5,6]
Output:
[4,5,6]
Note:
The list has 6 nodes. The two middle nodes are 3 and 4. We return the second middle node, which has value 4.
Example 3
Input:
head = [1]
Output:
[1]
Note:
The list has 1 node. The middle node is the 1st node, with value 1.
Constraints
1 and 100.1 <= Node.val <= 1000.Loading editor...