37. Middle of the Linked List
Return the middle node of a linked list. With two middle nodes, return the second one.
Example 1
Input:
head = [1,2,3,4,5]Output:
[3,4,5]Example 2
Input:
head = [1,2,3,4]Output:
[3,4]Hint 1
Fast and slow pointers: when fast reaches the end, slow is halfway.
Approach 1: Count then walk
Count n, then walk n/2 steps.
⏱ Time O(n)💾 Space O(1)
Approach 2: Fast & slow pointers ✅
One pass.
⏱ Time O(n)💾 Space O(1)
Reference solution for Fast & slow pointers (time O(n), space O(1)). Each solution passes every test in all four languages.
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next: # fast moves 2 steps for every 1 of slow
slow = slow.next
fast = fast.next.next
return slowclass Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
return slow;
}
}class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *slow = head, *fast = head;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
return slow;
}
};function middleNode(head) {
let slow = head, fast = head;
while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
return slow;
}Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.
This problem is explained in the lesson Linked Lists.
Run your code to see results here.