总结
- 有时候加个冗余头节点会大大降低实现难度，让代码变得更简洁。
- 做与链表相关的题目一定要在写代码前就想清楚算法的各个步骤，想好要保存哪些指针。否则很容易写乱。
- 要注意delete掉删除掉的节点，避免内存泄露。
Leetcode 2 Add Two Numbers
题意
用链表存储十进制数字的各位，现在给这样的两个链表，求和。
分析
由于链表头存的是最低位，所以我们可以同时扫描两个链表，模拟一下加法就行了。
假如用C++写的话，可以先开一个冗余头指针，方便实现。注意申请或释放内存时，应该要用new和delete而不要用malloc和free，养成良好的编程习惯。
假设两个链表的长度分别为n和m，那么时间复杂度和空间复杂度都是$O(n + m)$，显然空间复杂度可以优化到$O(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
| class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0);
ListNode *p = dummy;
int carry = 0;
while (l1 || l2) {
int x = l1 ? l1->val : 0;
int y = l2 ? l2->val : 0;
int sum = x + y + carry;
carry = sum / 10;
p->next = new ListNode(sum % 10);
p = p->next;
if (l1)
l1 = l1->next;
if (l2)
l2 = l2->next;
}
if (carry)
p->next = new ListNode(1);
p = dummy->next;
delete dummy;
return p;
}
};
|
Leetcode 19 Remove Nth Node From End of List
题意
给一个链表，要求删除倒数第n个节点。
分析
这道题的边界情况是删除链表首个节点。
我们用两个指针指向表头，然后让其中一个指针先走n步，假如走完n步后指向了空指针，说明删除的是表头。假如走完不是空指针，则让另外一个指针开始和它一步一步走，直到前面的指针指到了最后一个节点时，后面的指针刚好指向待删除节点的前一个节点。
这样做的时间复杂度是$O(n)$。
代码
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
| class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int k) {
if (head == nullptr || k <= 0)
return nullptr;
ListNode *behind = head, *ahead = head;
for (int i = 0; i < k; i++) {
ahead = ahead->next;
}
if (ahead == nullptr) {
ListNode *temp = head;
head = head->next;
delete(temp);
return head;
}
while (ahead->next != nullptr) {
ahead = ahead->next;
behind = behind->next;
}
ListNode *temp = behind->next;
behind->next = behind->next->next;
delete(temp);
return head;
}
};
|
Leetcode 21 Merge Two Sorted Lists
题意
合并两个有序链表。
分析
直接写就行了，时间复杂度为$O(n+m)$，其中n和m为两个链表的长度。
代码
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:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *dummy = new ListNode(0);
ListNode *p = dummy;
while(l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = l1 ? l1 : l2;
p = dummy->next;
delete(dummy);
return p;
}
};
|
Leetcode 23 Merge k Sorted Lists
题意
合并k个有序链表。
分析
我们需要一种数据结构来较快地插入一个数，取出最小的数，删除最小的数。不难想到优先队列可以满足这些要求。
假设k个链表的节点个数和为n，则时间复杂度为$O(nlogk)$。
代码
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
| class Solution {
private:
struct Node {
ListNode *p;
int idx;
Node(ListNode *p, int idx) {
this->p = p;
this->idx = idx;
}
bool operator < (const Node &rhs) const {
return p->val > rhs.p->val;
}
};
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<Node> que;
for (int i = 0; i < lists.size(); i++) {
if (lists[i]) {
que.push(Node(lists[i], i));
lists[i] = lists[i]->next;
}
}
ListNode *dummy = new ListNode(0);
ListNode *p = dummy;
while(!que.empty()) {
Node node = que.top();
que.pop();
if (lists[node.idx] != nullptr) {
int idx = node.idx;
que.push(Node(lists[idx], idx));
lists[idx] = lists[idx]->next;
}
p->next = node.p;
p = p->next;
}
p = dummy->next;
delete(dummy);
return p;
}
};
|
Leetcode 24 Swap Nodes in Pairs
题意
两两交换链表的相邻节点。
分析
递归来写，分三种情况，当前节点是空节点，当前节点没有后继，当前节点有后继。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
if (head->next == nullptr) {
return head;
}
ListNode *newHead = head->next;
ListNode *nex = head->next->next;
newHead->next = head;
head->next = swapPairs(nex);
return newHead;
}
};
|
Leetcode 25 Reverse Nodes in k-Group
题意
是Leetcode 24的升级版，需要将链表的每k个节点翻转。
分析
用迭代来写，先加个冗余头节点，方便实现。需要记录k节点组的前一个节点p，第一个节点head，最后一个节点tail。然后，我们不断地将p的后一个节点扔到tail的后面即可。
代码
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
| class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if (head == nullptr || head->next == nullptr || k < 2)
return head;
ListNode *dummy = new ListNode(0);
dummy->next = head;
ListNode *p = dummy, *tail = dummy, *temp = nullptr;
while (true) {
int count = 0;
while (count != k && tail != nullptr) {
tail = tail->next;
count++;
}
if (tail == nullptr) {
break;
}
head = p->next;
while (p->next != tail) {
temp = p->next;
p->next = temp->next;
temp->next = tail->next;
tail->next = temp;
}
p = tail = head;
}
p = dummy->next;
delete(dummy);
return p;
}
};
|
Leetcode 61 Rotate List
题意
回转链表，注意不是反转链表。
分析
分三步，首先求出链表长度以及最后一个节点，然后找到回转后的首个节点的前继，最后修改一下它们的指针即可。
代码
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
| class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr)
return nullptr;
ListNode *p = head, *lastNode;
int len = 1;
while (p->next) {
len++;
p = p->next;
lastNode = p;
}
k %= len;
if (k == 0)
return head;
k = len - k - 1;
ListNode *pre = head;
while (k--) {
pre = pre->next;
}
lastNode->next = head;
head = pre->next;
pre->next = nullptr;
return head;
}
};
|
Leetcode 82 Remove Duplicates from Sorted List II
题意
删除有序链表中的重复元素。
分析
申请个冗余节点会比较好实现点。
代码
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
| class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *dummy = new ListNode(0);
ListNode *p = dummy;
while (head) {
ListNode *p2 = head;
while (p2->next && p2->next->val == head->val) {
p2 = p2->next;
}
if (head != p2) {
while (head != p2) {
ListNode *temp = head->next;
delete(head);
head = temp;
}
head= p2->next;
delete(p2);
} else {
p->next = head;
p = p->next;
head = head->next;
p->next = nullptr;
}
}
ListNode *temp = dummy->next;
delete(dummy);
return temp;
}
};
|
Leetcode 83 Remove Duplicates from Sorted List
题意
删除有序链表中的多余的重复元素，即要保证每个元素最多出现一次。
分析
直接扫一遍就行了，注意delete掉删掉的节点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *cur = head;
while (cur && cur->next) {
if (cur->next->val == cur->val) {
ListNode *temp = cur->next;
cur->next = cur->next->next;
delete(temp);
} else {
cur = cur->next;
}
}
return head;
}
};
|
Leetcode 86 Partition List
留坑待填。