两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。LeetCode2
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(-1);
auto p = dummy;
int carry = 0;
while (l1 || l2 || carry) {
int n1 = l1 ? l1->val : 0;
int n2 = l2 ? l2->val : 0;
int sum = (n1 + n2 + carry) % 10;
carry = (n1 + n2 + carry) / 10;
p->next = new ListNode(sum);
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
p = p->next;
}
return dummy->next;
}
两数相加II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。LeetCode445
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1, s2; // 使用栈数据结构
for (auto p = l1; p; p = p->next) s1.push(p->val);
for (auto p = l2; p; p = p->next) s2.push(p->val);
int carry = 0;
ListNode* res = nullptr;
while (s1.size() || s2.size() || carry) {
int n1 = s1.size() ? s1.top() : 0;
if (s1.size()) s1.pop();
int n2 = s2.size() ? s2.top() : 0;
if (s2.size()) s2.pop();
int sum = (n1 + n2 + carry) % 10;
auto node = new ListNode(sum);
node->next = res;
res = node;
carry = (n1 + n2 + carry) / 10;
}
return res;
}
删除链表中的倒数第N个结点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。LeetCode19
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head) return nullptr;
auto dummy = new ListNode(-1);
dummy->next = head;
auto pre = dummy;
auto cur = head;
for (int i = 0; i < n; i++) cur = cur->next;
while (cur) {
pre = pre->next;
cur = cur->next;
}
pre->next = pre->next->next;
return dummy->next;
}
合并两个排序的链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。LeetCode21
参考代码
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
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(-1);
auto p = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
p = p->next;
} else {
p->next = l2;
l2 = l2->next;
p = p->next;
}
}
while (l1) {
p->next = l1;
l1 = l1->next;
p = p->next;
}
while (l2) {
p->next = l2;
l2 = l2->next;
p = p->next;
}
return dummy->next;
}
合并k个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。LeetCode23
参考代码
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
57
58
59
60
61
62
63
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
// 分治 时间复杂度 O(knlogk)
ListNode* merge(vector<ListNode*>& lists, int l, int r) {
if (l == r) return lists[l];
if (l < r) {
int mid = (l + r) >> 1;
return mergeLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
return nullptr;
}
ListNode* mergeLists(ListNode* l1, ListNode* l2) {
auto dummy = new ListNode(-1);
auto p = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
p = p->next;
} else {
p->next = l2;
l2 = l2->next;
p = p->next;
}
}
while (l1) {
p->next = l1;
l1 = l1->next;
p = p->next;
}
while (l2) {
p->next = l2;
l2 = l2->next;
p = p->next;
}
return dummy->next;
}
// 逐个合并
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (!lists.size()) return nullptr;
auto dummy = new ListNode(-1);
auto p = dummy;
while (true) {
int minV = INT_MAX;
bool flag = true;
int idx = 0;
for (int i = 0; i < lists.size(); i++) {
if (lists[i] && lists[i]->val < minV) {
minV = lists[i]->val;
idx = i;
flag = false;
}
}
if (flag) break;
p->next = lists[idx];
lists[idx] = lists[idx]->next;
p = p->next;
}
return dummy->next;
}
两两交换链表中的结点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。LeetCode24
参考代码
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 递归
* 时间复杂度：O(n)
* 空间复杂度：O(n)
*/
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
auto t = head->next;
head->next = swapPairs(t->next);
t->next = head;
return t;
}
/**
* 迭代
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
ListNode* swapPairs(ListNode* head) {
if (!head || !head->next) return head;
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
auto cur = head;
while (cur && cur->next) {
auto nx = cur->next;
cur->next = nx->next;
nx->next = cur;
p->next = nx;
p = cur;
cur = cur->next;
}
return dummy->next;
}
};
k个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。LeetCode25
参考代码
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
ListNode* reverseKGroup(ListNode* head, int k) {
if (!head) return head;
auto a = head, b = head;
// 寻找区间
for (int i = 0; i < k; i++) {
if (!b) return head; // 不够k
b = b->next;
}
// 翻转区间
ListNode* pre = nullptr;
auto cur = a;
while (cur != b) {
auto nx = cur->next;
cur->next = pre;
pre = cur;
cur = nx;
}
a->next = reverseKGroup(b, k);
return pre;
}
};
反转链表
反转一个单链表。LeetCode206
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
auto cur = head;
while (cur) {
auto nx = cur->next;
cur->next = pre;
pre = cur;
cur = nx;
}
return pre;
}
/**
* 递归版本
*/
ListNode* reverseList(ListNode* head) {
if (!head) return;
auto last = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return last;
}
反转链表II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。LeetCode92
参考代码
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (!head) return head;
auto dummy = new ListNode(-1);
dummy->next = head;
auto a = dummy, b = head;
for (int i = 0; i < m - 1; i++) a = a->next; // 前一个结点，便于将翻转的区间连接起来
for (int i = 0; i < n; i++) b = b->next; // 正常遍历即可
auto cur = a->next, pre = b; // 注意cur需要向后走一步，pre是之后的结点
while (cur != b) { //翻转区间
auto nx = cur->next;
cur->next = pre;
pre = cur;
cur = nx;
}
a->next = pre; // 将前面和后面部分连接起来
return dummy->next;
}
/**
* 递归
* 将链表向后移动，直到m当作链表头结点，然后翻转链表前n-m个结点
*/
ListNode* pos; // 记录翻转区间的后一个结点
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (m == 1) return reverseN(head, n);
head->next = reverseBetween(head, m - 1, n - 1);
return head;
}
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
pos = head->next;
return head;
}
auto last = reverseN(head->next, n - 1);
head->next->next = head;
head->next = pos;
return last;
}
};
反转链表的前n个结点
翻转链表中的前n个结点
参考代码
1
2
3
4
5
6
7
8
9
10
11
ListNode* pos; // 记录翻转区间的后一个结点
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
pos = head->next;
return head;
}
auto last = reverseN(head->next, n - 1);
head->next->next = head;
head->next = pos;
return last;
}
旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。LeetCode61
参考代码
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
ListNode* rotateRight(ListNode* head, int k) {
if (!head) return head;
int len = 0;
auto p = head, q = head;
// 统计链表的长度
for (; p->next; p = p->next) len++;
len++;
k %= len; // 取余提高效率
p->next = head; // 构建循环链表
// 寻找断开的前一个结点
for (int i = 0; i < len - k - 1; i++) q = q->next;
auto nx = q->next;
q->next = nullptr;
return nx;
}
};
删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。LeetCode83
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
ListNode* deleteDuplicates(ListNode* head) {
auto cur = head;
while (cur) {
if (cur->next && cur->val == cur->next->val)
cur->next = cur->next->next;
else
cur = cur->next;
}
return head;
}
};
删除排序链表中的重复元素II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。LeetCode82
参考代码
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
auto dummy = new ListNode(-1);
dummy->next = head;
auto pre = dummy, cur = head;
while (cur->next) {
if (cur->val != cur->next->val) { // 如果当前结点和下一个结点不同时进行判断
if (pre->next != cur) pre->next = cur->next; // 如果pre的next指针指向的不是cur，则说明有重复
else pre = cur; // 否则没有重复
}
cur = cur->next;
}
if (pre->next != cur) pre->next = cur->next; // 特殊情况，所有元素都相同的时候
return dummy->next;
}
};
分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。LeetCode86
参考代码
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
ListNode* partition(ListNode* head, int x) {
if (!head) return nullptr;
ListNode* l1 = new ListNode(0); // 小于x的结点
ListNode* l2 = new ListNode(0); // 大于等于x的阶段，
auto p1 = l1;
auto p2 = l2;
while (head) {
if (head->val < x) {
p1->next = head;
p1 = p1->next;
} else {
p2->next = head;
p2 = p2->next;
}
head = head->next;
}
// 特判
if (p1 == l1) return l2->next;
if (p2 == l2) return l1->next;
p1->next = l2->next;
p2->next = nullptr;
return l1->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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
vector<int> nodes;
while (head) {
nodes.push_back(head->val);
head = head->next;
}
return dfs(nodes, 0, nodes.size() - 1);
}
TreeNode* dfs(vector<int>& nodes, int l, int r) {
if (l > r) return nullptr;
int mid = (l + r) >> 1;
auto root = new TreeNode(nodes[mid]);
root->left = dfs(nodes, l, mid - 1);
root->right = dfs(nodes, mid + 1, r);
return root;
}
};
复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。LeetCode138
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Node* copyRandomList(Node* head) {
// 复制结点
for (auto p = head; p;) {
auto np = new Node(p->val);
auto next = p->next;
p->next = np;
np->next = next;
p = next;
}
// 更新Random指针
for (auto p = head; p; p = p->next->next)
if (p->random) p->next->random = p->random->next;
// 拆分链表
auto dummy = new Node(-1);
auto cur = dummy;
for (auto p = head; p;) {
auto pre = p;
cur->next = p->next;
cur = cur->next;
p = p->next->next;
pre->next = p; // 还原原链表
}
return dummy->next;
}
环形链表
给定一个链表，判断链表中是否有环。LeetCode141
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
bool hasCycle(ListNode* head) {
ListNode *f, *s;
f = s = head;
while (f && f->next) {
f = f->next->next;
s = s->next;
if (f == s) return true;
}
return false;
}
};
环形链表II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。LeetCode142
参考代码
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
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *f, *s;
f = s = head;
while (f && f->next) { // 寻找相遇的结点
f = f->next->next;
s = s->next;
if (s == f) break;
}
// 判断是否有环
if (!f || !f->next) return nullptr;
s = head; // 慢指针设置为头结点
// 一同遍历，再次相遇时即为第一个公共结点
while (s != f) {
s = s->next;
f = f->next;
}
return s;
}
};
重排链表(中等)
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。重排链表
参考代码
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
57
58
59
60
61
62
63
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 使用辅助数组
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
void reorderList(ListNode* head) {
vector<ListNode*> tmp;
for (auto p = head; p; p = p->next) tmp.push_back(p);
int l = 0, r = tmp.size() - 1;
while (l < r) {
tmp[l]->next = tmp[r];
l++;
if (l == r) break;
tmp[r]->next = tmp[l];
r--;
}
tmp[l]->next = nullptr; // 注意这儿需要置空
}
/**
* 找中点 翻转后面部分，再合并
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
void reorderList(ListNode* head) {
if (!head) return;
ListNode *f, *s;
f = s = head;
// 寻找中点
while (f && f->next) {
f = f->next->next;
s = s->next;
}
// 记录后半部分链表
auto post = s->next;
s->next = nullptr; // 将前后部分链表断开
// 翻转链表
ListNode* pre = nullptr;
while (post) {
auto nx = post->next;
post->next = pre;
pre = post;
post = nx;
}
// 合并链表
while (pre) {
auto th = head->next;
auto tp = pre->next;
head->next = pre;
pre->next = th;
head = th;
pre = tp;
}
}
};
对链表进行插入排序
对链表进行插入排序。LeetCode147
参考代码
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (!head || !head->next) return head;
auto dummy = new ListNode(-1); // 构建虚拟结点，头结点可能会变
dummy->next = head;
auto pre = head;
auto cur = head->next;
while (cur) {
// 如果当前待排序的结点的值小于排序部分的最后一个结点的值则需要从前向后找待排序结点的位置
if (cur->val < pre->val) {
auto t = dummy;
// 从头开始遍历，寻找可以插入的位置
while (t->next->val < cur->val) t = t->next;
// 插入结点
pre->next = cur->next;
cur->next = t->next;
t->next = cur;
cur = pre->next;
} else { // 否则，直接排序下一个结点
pre = pre->next;
cur = cur->next;
}
}
return dummy->next;
}
};
归并排序链表(归并)
在 $O(n log n)$ 时间复杂度和常数级空间复杂度下，对链表进行排序。LeetCode148
参考代码
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 思路：自底向上的归并排序，使用循环
*
* 时间复杂度：O(nlogn)
* 空间复杂度：O(1)
*/
ListNode* sortList(ListNode* head) {
int n = 0;
for (auto p = head; p; p = p->next) n++;
auto dummy = new ListNode(-1);
dummy->next = head;
// 枚举区间长度
for (int i = 1; i < n; i *= 2) {
auto cur = dummy;
// 遍历所有区间
for (int j = 0; j + i < n; j += i * 2) {
auto first = cur->next, second = first;
// 寻找下一个区间的起点
for (int k = 0; k < i; k++) second = second->next;
int f = 0, s = 0;
// 归并两个区间
while (f < i && s < i && second) {
if (first->val <= second->val) {
cur->next = first;
cur = first;
first = first->next;
f++;
} else {
cur->next = second;
cur = second;
second = second->next;
s++;
}
}
while (f < i) {
cur->next = first;
cur = first;
first = first->next;
f++;
}
while (s < i && second) {
cur->next = second;
cur = second;
second = second->next;
s++;
}
// 指向下一个区间
cur->next = second;
}
}
return dummy->next;
}
/**
* 递归版本
* 时间复杂度：O(nlogn)
* 空间复杂度：O(logn)
*/
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head; // 边界条件
auto s = head;
auto f = head;
// 快慢指针找中间结点
while (!f || !f->next) {
f = f->next->next;
s = s->next;
}
auto t = s->next; // 断开链表
s->next = nullptr;
auto l = sortList(head); // 递归排序前部分
auto r = sortList(t); // 递归排序后部分
auto dummy = new ListNode(-1); // 构建虚拟结点
auto cur = dummy;
// 归并两部分
while (l && r) {
if (l->val < r->val) {
cur->next = l;
l = l->next;
cur = cur->next;
} else {
cur->next = r;
r = r->next;
cur = cur->next;
}
}
while (l) {
cur->next = l;
l = l->next;
cur = cur->next;
}
while (r) {
cur->next = r;
r = r->next;
cur = cur->next;
}
return dummy->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
class Solution {
public:
ListNode* quickSortList(ListNode* head) {
//链表快速排序
if (!head || !head->next) return head;
qsortList(head, nullptr);
return head;
}
void qsortList(ListNode* head, ListNode* tail) {
//链表范围是[low, high)
if (head != tail && head->next != tail) {
ListNode* mid = partitionList(head, tail);
qsortList(head, mid);
qsortList(mid->next, tail);
}
}
ListNode* partitionList(ListNode* low, ListNode* high) {
//链表范围是[low, high)
int key = low->val;
ListNode* loc = low;
for (ListNode* i = low->next; i != high; i = i->next)
if (i->val < key) {
loc = loc->next;
swap(i->val, loc->val);
}
swap(loc->val, low->val);
return loc;
}
};
相交链表(两个链表的第一个公共结点)
编写一个程序，找到两个单链表相交的起始节点。LeetCode160
1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
auto p = headA, q = headB;
while (p != q) {
if (p)
p = p->next;
else
p = headB;
if (q)
q = q->next;
else
q = headA;
}
return p;
}
移除链表元素
删除链表中等于给定值 val 的所有节点。LeetCode203
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* removeElements(ListNode* head, int val) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto cur = head, pre = dummy;
while (cur) {
if (cur->val == val) {
pre->next = cur->next;
cur = cur->next;
} else {
pre = pre->next;
cur = cur->next;
}
}
return dummy->next;
}
删除链表中的结点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。LeetCode237
参考代码
1
2
3
4
5
void deleteNode(ListNode* node) {
// 转换为删除下一个结点
node->val = node->next->val;
node->next = node->next->next;
}
回文链表
请判断一个链表是否为回文链表。LeetCode234
参考代码
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
/**
* 找中点，翻转后半段，然后比较
* 时间复杂度：O(n)
* 空间复杂度：O(1)
*/
bool isPalindrome(ListNode* head) {
auto f = head, s = head;
while (f && f->next) {
f = f->next->next;
s = s->next;
}
if (f) s = s->next;
ListNode* pre = nullptr;
while (s) {
auto nx = s->next;
s->next = pre;
pre = s;
s = nx;
}
f = head;
while (pre) {
if (pre->val != f->val) return false;
pre = pre->next;
f = f->next;
}
return true;
}
ListNode* left;
/**
* 时间复杂度：O(n)
* 空间复杂度：O(n) 栈空间
*/
bool isPalindrome(ListNode* head) {
left = head;
return helper(head);
}
bool helper(ListNode* head) {
if (!head) return true;
bool res = helper(head->next);
res = res && (left->val == head->val);
left = left->next;
return res;
}
};
从尾到头打印链表
从尾到头打印链表。
参考代码
1
2
3
4
5
6
7
8
9
10
11
vector<int> res;
vector<int> reversePrint(ListNode* head) {
dfs(head);
return res;
}
// 后序遍历
void dfs(ListNode* head) {
if (!head) return;
dfs(head->next);
res.push_back(head->val);
}
链表中的倒数第k个结点
链表中的倒数第k个结点。
参考代码
1
2
3
4
5
6
7
8
9
10
ListNode* getKthFromEnd(ListNode* head, int k) {
ListNode *s, *f;
f = s = head;
for (int i = 0; i < k; i++) f = f->next;
while (f) {
f = f->next;
s = s->next;
}
return s;
}
奇偶链表
给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。LeetCode328
参考代码
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
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* oddEvenList(ListNode* head) {
if (!head || !head->next) return head;
auto p1 = head, p2 = head->next; // 分别是奇数链表和偶数链表的头结点
auto p = p2, cur = p2->next; // p是偶数链表的头结点，cur是当前结点
if (p2) p2->next = nullptr;
int cnt = 1;
while (cur) {
auto t = cur->next;
// 奇数结点
if (cnt % 2) {
p1->next = cur;
p1 = p1->next;
if (p1) p1->next = nullptr;
} else { // 偶数结点
p2->next = cur;
p2 = p2->next;
if (p2) p2->next = nullptr;
}
cur = t;
cnt++;
}
// 拼起来
p1->next = p;
return head;
}
};
