876. Middle of the Linked List
Problem Description
The task is to write a function that, given the head of a singly linked list, finds and returns the middle node of the list. A singly linked list is a collection of nodes where each node contains a value and a reference to the next node in the sequence. The key characteristic of this list is that you can only traverse it in one direction: from the head towards the end.
The challenge here is determining the middle node in a single pass, since the size of the list is not given in advance. It's also specified that if the linked list has an even number of nodes, we should return the second of the two middle nodes.
Intuition
To solve this problem efficiently, we make use of two pointers: slow
and fast
. Both pointers start at the head of the linked list. The fast
pointer moves through the list at twice the speed of the slow
pointer. This means that for every node the slow
pointer travels, the fast
pointer moves two nodes.
As a result of these different speeds, when the fast
pointer reaches the end of the list, the slow
pointer will be positioned at the middle. This happens because the fast
pointer traverses two nodes for every single step taken by the slow
pointer. If the total number of nodes is odd, the fast
pointer will eventually point to None
, which is the end of the list. If the number of nodes is even, the fast
pointer will point to the last node. In both cases, the slow
pointer will be at the middle, where if there are two middle nodes, because fast
moves two steps at a time, slow
will end up at the second middle node.
This approach allows us to find the middle node in a single pass through the list, which is more efficient than first counting the nodes and then traversing again to the middleāespecially in the case of very large lists.
Learn more about Linked List and Two Pointers patterns.
Solution Approach
The given solution makes use of two pointers, slow
and fast
, both initialized to the head
of the list. This approach is commonly known as the "tortoise and hare" algorithm. Let's go through the steps of this approach:
-
Both
slow
andfast
are initialized at thehead
of the linked list, thus they start at the same position. -
We then enter a loop that continues until
fast
is no longer pointing to a valid node orfast.next
isNone
. This condition ensures that we stop whenfast
(which moves faster) has reached the end of the list. -
Inside the loop,
slow
is incremented to the next node (slow.next
) andfast
is incremented two nodes ahead (fast.next.next
).slow = slow.next
moves theslow
pointer one step forward.fast = fast.next.next
moves thefast
pointer two steps forward.
-
When
fast
reaches the end of the list or there are no more nodes to traverse (fast
becomesNone
orfast.next
isNone
), the loop ends. -
At this point,
slow
will be at the middle node of the list. If there are an odd number of nodes, it will be the exact middle. If there are an even number of nodes, it will be the second of the two middle nodes because of the wayfast
is moving two steps at a time. -
The function then returns the
slow
pointer, which now points to the middle node of the linked list.
No additional data structure is used, making the space complexity O(1), as we only have two pointers regardless of the size of the linked list. Since each node is visited once by either slow
or fast
, the time complexity is O(n), where n is the number of nodes in the list.
The beauty of this solution lies in its simplicity and efficiency. It effectively halves the traversal time to find the middle node, which would otherwise take longer if we first counted the entire list to find the length, and then iterated again to the middle.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach:
Suppose we have a singly linked list with 7 nodes, and their values when traversed from head to tail are [1, 2, 3, 4, 5, 6, 7]
. We want to determine the middle node in a single pass.
We initialize two pointers at the start, slow
points to the node with the value 1
, and fast
also points to the node with value 1
.
As we loop through the list:
- In the first step,
slow
will move one node and point to2
;fast
will move two nodes and point to3
. - In the second step,
slow
will move to3
;fast
to5
. - In the third step,
slow
moves to4
,fast
moves to7
. - Now,
fast
is pointing at the last node, andfast.next
isNone
. Thus, we reach the condition to end the loop.
At this point, slow
is pointing to 4
, which is the middle node in this list of 7 nodes. Our function would then return the node with the value 4
as the middle node.
Now, let's consider an even-numbered list with 6 nodes, where the values are [1, 2, 3, 4, 5, 6]
.
- On starting, both
slow
andfast
point to1
. - In the first step,
slow
moves to2
;fast
jumps to3
. - In the second step,
slow
goes to3
;fast
skips to5
. - In the third step,
slow
proceeds to4
andfast
jumps to the last node,6
. fast.next
is nowNone
. The loop ends.
Slow
is at the value 4
, which is the second of the two middle nodes in this list of 6 nodes, meeting our requirement to return the second middle node in the case of an even-numbered list.
With this explanation, it should be clear how the "tortoise and hare" algorithm functions, allowing us to find the middle of the list in a single pass, hence delivering an efficient solution.
Solution Implementation
1# Class definition for a singly-linked list node.
2class ListNode:
3 def __init__(self, value=0, next_node=None):
4 self.value = value
5 self.next_node = next_node
6
7class Solution:
8 def middleNode(self, head: ListNode) -> ListNode:
9 # Initialize two pointers, both starting at the head of the list.
10 # 'slow' will move one step at a time, and 'fast' will move two steps at a time.
11 slow_pointer = fast_pointer = head
12
13 # Traverse the list. The loop runs until 'fast' reaches the end of the list.
14 while fast_pointer and fast_pointer.next_node:
15 # Move 'slow' one step forward.
16 slow_pointer = slow_pointer.next_node
17 # Move 'fast' two steps forward.
18 fast_pointer = fast_pointer.next_node.next_node
19
20 # When 'fast' reaches the end, 'slow' will be at the middle node.
21 return slow_pointer
22
1// Definition for singly-linked list.
2class ListNode {
3 int value;
4 ListNode next;
5
6 // Constructor with no parameters
7 ListNode() {}
8
9 // Constructor with value parameter
10 ListNode(int value) {
11 this.value = value;
12 }
13
14 // Constructor with value and next node parameters
15 ListNode(int value, ListNode next) {
16 this.value = value;
17 this.next = next;
18 }
19}
20
21public class Solution {
22
23 /**
24 * Finds the middle node of a singly linked list.
25 *
26 * @param head The head of the linked list.
27 * @return The middle node of the linked list.
28 */
29 public ListNode middleNode(ListNode head) {
30 // Initialize two pointers, slow and fast.
31 ListNode slowPointer = head;
32 ListNode fastPointer = head;
33
34 // Iterate through the list.
35 // Fast pointer moves two steps at a time, slow pointer one step at a time.
36 while (fastPointer != null && fastPointer.next != null) {
37 slowPointer = slowPointer.next; // Move slow pointer one step
38 fastPointer = fastPointer.next.next; // Move fast pointer two steps
39 }
40
41 // When fast pointer reaches the end of the list,
42 // slow pointer will be at the middle element.
43 return slowPointer;
44 }
45}
46
1/**
2 * Definition for a singly-linked list node.
3 */
4struct ListNode {
5 int val; // The value the node stores
6 ListNode *next; // Pointer to the next list node in the linked list
7
8 // Constructor to initialize a node with no next node
9 ListNode() : val(0), next(nullptr) {}
10
11 // Constructor to initialize a node with a specific value and no next node
12 ListNode(int x) : val(x), next(nullptr) {}
13
14 // Constructor to initialize a node with a specific value and a next node
15 ListNode(int x, ListNode *next) : val(x), next(next) {}
16};
17
18class Solution {
19public:
20 /**
21 * Finds the middle node of a singly linked list.
22 * If there are two middle nodes, the second middle node is returned.
23 *
24 * @param head The head of the linked list.
25 * @return The middle node of the linked list
26 */
27 ListNode* middleNode(ListNode* head) {
28 ListNode *slow = head; // 'slow' pointer moves one node at a time
29 ListNode *fast = head; // 'fast' pointer moves two nodes at a time
30
31 // Continue until 'fast' reaches the end of the list
32 while (fast != nullptr && fast->next != nullptr) {
33 slow = slow->next; // Move 'slow' by one node
34 fast = fast->next->next; // Move 'fast' by two nodes
35 }
36
37 // When 'fast' reaches the end, 'slow' will be at the middle node
38 return slow;
39 }
40};
41
1// Definition for singly-linked list node.
2interface ListNode {
3 val: number;
4 next: ListNode | null;
5}
6
7/**
8 * Finds the middle node of a singly linked list.
9 * @param head The head of the singly linked list.
10 * @return The middle node of the list.
11 */
12function middleNode(head: ListNode | null): ListNode | null {
13 let fastPointer: ListNode | null = head; // Pointer that will move two steps at a time
14 let slowPointer: ListNode | null = head; // Pointer that will move one step at a time
15
16 // Loop until the fast pointer reaches the end of the list
17 while (fastPointer !== null && fastPointer.next !== null) {
18 fastPointer = fastPointer.next.next; // Move fast pointer two steps
19 slowPointer = slowPointer.next; // Move slow pointer one step
20 }
21
22 // When the fast pointer reaches the end of the list,
23 // the slow pointer will be at the middle
24 return slowPointer;
25}
26
Time and Space Complexity
The time complexity of the given code is O(n)
, where n
is the number of nodes in the linked list. This is because the fast pointer advances two steps at a time and the slow pointer advances one step at a time. They start at the same point, so when the fast pointer reaches the end of the list, the slow pointer must be at the middle. Since the fast pointer traverses at most n
nodes (where n
is even) or n-1
nodes (where n
is odd), and it takes two iterations of the loop to move the fast pointer two nodes ahead, the loop executes approximately n/2
iterations, which is linear with respect to the number of nodes.
The space complexity is O(1)
irrespective of the number of nodes in the linked list because only two additional pointers (variables slow
and fast
) are used, which occupy constant space.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!