Sponsored
Sponsored
This technique uses two pointers, 'slow' and 'fast'. Both start at the head of the list. The 'slow' pointer progresses 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 at the middle node. This works because the 'fast' pointer traverses the list twice as fast as the 'slow' pointer, thus splitting the path lengthwise in half.
Time Complexity: O(n), where n is the number of nodes in the list, because we are iterating through the list once.
Space Complexity: O(1), since we are using a constant amount of space.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def middleNode(self, head: ListNode) -> ListNode:
8 slow = head
9 fast = head
10 while fast and fast.next:
11 slow = slow.next
12 fast = fast.next.next
13 return slowPython's solution involves defining a ListNode class for the nodes of the linked list. The 'middleNode' function executes the two-pointer technique, returning the middle node when 'fast' reaches the list's end.
This approach involves two passes over the list. The first pass calculates the total number of nodes. In the second pass, we traverse halfway through the list to reach the middle node by stopping at n/2, where n is the number of nodes. This explicitly determines the node that marks the middle of the list.
Time Complexity: O(n) for two full passes through the list.
Space Complexity: O(1) as only a few extra variables are used.
1 public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null) {
this.val = val;
this.next = next;
}
}
public class Solution {
public ListNode MiddleNode(ListNode head) {
int length = 0;
ListNode temp = head;
while (temp != null) {
length++;
temp = temp.next;
}
int halfLength = length / 2;
temp = head;
for (int i = 0; i < halfLength; i++) {
temp = temp.next;
}
return temp;
}
}C# matches the previous pattern of counting nodes to determine list length before rerunning half of it to identify the middle node for return.