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:
1
2
3
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Constraints:
- The number of nodes in the list is in the range
[1, 100]. 1 <= Node.val <= 100
Solution
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ListNode *middle_node::middleNode(ListNode *head) {
// 空链表
if (head == nullptr) {
return nullptr;
}
// 单个node
if (head->next == nullptr) {
return head;
}
map<int, ListNode*> m;
ListNode* node = head;
int i = 0;
while (node != nullptr) {
m[i] = node;
node = node->next;
i++;
}
int middleIndex = i % 2 == 0 ? (i / 2) : (i - 1) / 2;
return m.find(middleIndex)->second ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode *middle_node::middleNodeSlowFastPointers(ListNode *head) {
/*
* fast走n步到达索引为2n的位置停止（如果总node数量为N，那么2n = N - 1, 或者2n = N）, 那么（n = (N - 1) / 2, N为奇数； n = N / 2, N为偶数，n刚好满足问题的答案）
* slow此时到达索引为n的位置
* */
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
References
https://leetcode.com/problems/middle-of-the-linked-list/?envType=study-plan&id=level-1