title: “[刷题]链表专题”
tags: 数据结构与算法
abbrlink: 6db30a46
date: 2019-02-12 21:23:22
[Leetcode 141, 142] 环形链表，环形链表 II （剑指Offer面试题23）
解法：(链表遍历，快慢指针)
- 判环：快慢指针，快指针+2， 慢指针+1，若快指针在到达链表尾(不带环的才有链表尾)之前与慢指针相遇，则有环。
- 找入口：快慢指针第一次相遇节点与头结点之间的节点数与环中节点数相同，两个指针一个从链表头开始，一个从相遇节点开始遍历，两个指针再次相遇节点为入口节点。
代码：
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
40
41
42
43
44
45
46
47
48/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// 找入口
ListNode *detectCycle(ListNode *head) {
if(!JudgeCycle(head)) return nullptr;
ListNode *pFirstptr = head;
//第一次相遇节点位置就是环内节点数
while(pFirstptr != pMeetNode){
pFirstptr = pFirstptr -> next;
pMeetNode = pMeetNode -> next;
}
return pFirstptr;
}
// 判环
bool JudgeCycle(ListNode *head){
if(head == nullptr) return false;
ListNode *pFastptr = head;
ListNode *pSlowptr = head;
while(pFastptr -> next && pFastptr -> next -> next){
pFastptr = pFastptr -> next -> next;
pSlowptr = pSlowptr -> next;
if(pFastptr == pSlowptr){
pMeetNode = pFastptr;
return true;
}
}
return false;
}
private:
ListNode *pMeetNode;
};
[Leetcode 206] 反转链表 (剑指Offer面试题24)
- 解法：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode* h = NULL;
ListNode* p = pHead;
while(p){
ListNode* tmp = p -> next;
p -> next = h;
h = p;
p = tmp;
}
return h;
}
};
[Leetcode 21] 合并两个有序链表 (剑指Offer面试题 25)
解法：
- 优先队列重排 (可参考 提交记录99%代码)
- 比较插入列表 （这里使用）
代码：
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == nullptr && l2 == nullptr)
return nullptr;
if(l1 == nullptr && l2 != nullptr)
return l2;
if(l2 == nullptr && l1 != nullptr)
return l1;
ListNode* res;
ListNode* pMergeNode;
if(l1->val < l2->val){
pMergeNode = l1;
l1 = l1->next;
}
else{
pMergeNode = l2;
l2 = l2->next;
}
res = pMergeNode;
while(true){
if(l1 == nullptr && l2 != nullptr){
pMergeNode->next = l2;
break;
}
if(l2 == nullptr && l1 != nullptr){
pMergeNode->next = l1;
break;
}
if(l1 == nullptr && l2 == nullptr){
break;
}
if(l1->val < l2->val){
pMergeNode->next = l1;
l1 = l1->next;
}else{
pMergeNode->next = l2;
l2 = l2->next;
}
pMergeNode = pMergeNode->next;
}
return res;
}
};
[Leetcode23] 合并K个排序链表
解法：
- 优先队列或列表遍历插入，优先队列效率相对高一些，这里列出的是列表遍历比较插入的代码，优先队列可参考提交记录99%代码。
代码：
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
40
41
42/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* res;
ListNode* pMerge = new ListNode(0);
res = pMerge;
while(!isAllNodeEnd(lists)){
int tmp = INT_MAX;
int index = 0;
for(int i = 0; i < lists.size() ; i++){
if(lists[i] != nullptr){
if(lists[i]->val < tmp){
tmp = lists[i]->val;
index = i;
}
}
}
pMerge->next = lists[index];
pMerge = pMerge->next;
lists[index] = lists[index]->next;
}
return res->next;
}
bool isAllNodeEnd(vector<ListNode*>& lists){
for(auto item : lists){
if(item != nullptr)
return false;
}
return true;
}
};
