876、链表的中间节点
[链表的中间节点][https://leetcode.cn/problems/middle-of-the-linked-list/]
给你单链表的头结点 head ，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
慢指针每次前进一格，快指针每次前进两格
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
|
141、环形链表
[环形链表][https://leetcode.cn/problems/linked-list-cycle/]
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
如果快慢指针可以相遇，则有环
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(fast == slow){
return true;
}
}
return false;
}
};
|
142、环形链表2
[环形链表2][https://leetcode.cn/problems/linked-list-cycle-ii/]
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
当快慢指针相遇时，让慢指针和头节点继续走，他们直接相隔一个环长的倍数，当两者相遇，即是初始点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
if(fast == slow){
while(head != slow){
head = head->next;
slow = slow->next;
}
return head;
}
}
return NULL;
}
};
|
143、重排链表
[重排链表][https://leetcode.cn/problems/reorder-list/]
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
1
| L0 → L1 → … → Ln - 1 → Ln
|
请将其重新排列后变为：
1
| L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
|
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
先找到中间节点，然后反转后面部分
用head 代表前面链表的头节点
用head2代表后面链表的头节点
head->next = head2;
head2->next = head->next;
因为节点值会变化，所以需要提前存储这两个值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution {
public:
void reorderList(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
ListNode* pre = NULL;
ListNode* cur = slow;
while(cur){
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
ListNode* head2 = pre;
while(head2->next){
ListNode* next1 = head->next;
ListNode* next2 = head2->next;
head->next = head2;
head2->next = next1;
head = next1;
head2 = next2;
}
}
};
|
