Problem
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(s)
Consider the following example(s) to understand the expected input and output.Input
head = [1,2,3,4,5] Output
[3,4,5] Solution
This solution uses the Two Pointer technique with a slow pointer and a fast pointer. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.When the fast pointer reaches the end of the list, the slow pointer will be positioned at the middle node. For an even-sized list, the fast pointer reaches the end after the slow pointer has moved to the second middle node.
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
Complexity
The fast pointer moves through the linked list at twice the speed of the slow pointer, and the list is traversed only once. Therefore, the time complexity isO(n).
The algorithm uses only two pointers regardless of the size of the linked list, resulting in an extra space complexity of
O(1).