介绍
链表是一种顺序存取结构，即访问第 $i$ 个元素需要先访问前 $i-1$ 个元素，即元素访问的时间复杂度为 $\mathcal{O}(n)$，但是优势是在某个位置删除和增加结点的时间复杂度为 $\mathcal{O}(1)$。
单链表
1
2
3
4
5
6
7
|
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
|
1
2
3
4
|
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
|
构建链表
- 头插法：构建的链表的元素与输入的元素方向相反。
- 尾插法：构建的链表的元素与输入的元素方向相同。
经典问题
在实际的问题中，一般很少需要主动构建链表解题，除非是问题就是针对链表设计的，虽然很少使用到链表，但是关于链表的题目大多都很经典。
LeetCode 链表专题
2. 两数相加
https://leetcode.cn/problems/add-two-numbers/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
vhead = ListNode()
vp = vhead
pre = 0
while l1 and l2:
pre, l1.val = divmod(l1.val + l2.val + pre, 10)
vp.next = l1
vp, l1, l2 = vp.next, l1.next, l2.next
if not l1:
l1 = l2
while l1:
pre, l1.val = divmod(l1.val + pre, 10)
vp.next = l1
vp, l1 = vp.next, l1.next
if pre:
vp.next = ListNode(pre)
return vhead.next
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
auto divmod = [](int x, int base) -> pair<int, int> { return {x / base, x % base}; };
auto vhead = new ListNode(), vp = vhead;
int pre = 0;
while (l1 && l2) {
tie(pre, l1->val) = divmod(l1->val + l2->val + pre, 10);
vp->next = l1, vp = vp->next, l1 = l1->next, l2 = l2->next;
}
if (!l1) { l1 = l2; }
while (l1) {
tie(pre, l1->val) = divmod(l1->val + pre, 10);
vp->next = l1, vp = vp->next, l1 = l1->next;
}
if (pre) { vp->next = new ListNode(pre); }
return vhead->next;
}
};
|
- 时间复杂度：$\mathcal{O}(\max(n_1,n_2))$，$n_1,n_2$ 分别为链表
l1 和 l2 的结点数。
- 空间复杂度：$\mathcal{O}(1)$
19. 删除链表的倒数第 N 个结点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
vhead = ListNode()
first = second = vhead
k = 0
vhead.next = head
while first:
if k > n:
second = second.next
first = first.next
k += 1
second.next = second.next.next
return vhead.next
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
auto vhead = new ListNode();
auto first = vhead, second = vhead;
int k = 0;
vhead->next = head;
while (first) {
if (k++ > n) {
second = second->next;
}
first = first->next;
}
second->next = second->next->next;
return vhead->next;
}
};
|
- 时间复杂度：$\mathcal{O}(n)$
- 空间复杂度：$\mathcal{O}(1)$
21. 合并两个有序链表
https://leetcode.cn/problems/merge-two-sorted-lists/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
vhead = ListNode()
p = vhead
while l1 and 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 or l2
return vhead.next
|
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* mergeTwoLists(ListNode* l1, ListNode* l2) {
auto vhead = new ListNode(), p = vhead;
while (l1 && l2) {
if (l1->val <= l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
if (!l1) l1 = l2;
p->next = l1;
return vhead->next;
}
};
|
- 时间复杂度：$\mathcal{O}(n)$
- 空间复杂度：$\mathcal{O}(1)$
141. 环形链表
https://leetcode.cn/problems/linked-list-cycle/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next:
return False
first = head.next.next
second = head
while first and first.next:
if first == second:
return True
second = second.next
first = first.next.next
return False
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public:
bool hasCycle(ListNode *head) {
if (!head || !head->next) {
return false;
}
auto first = head->next->next, second = head;
while (first && first->next) {
if (first == second) {
return true;
}
first = first->next->next;
second = second->next;
}
return false;
}
};
|
- 时间复杂度：$\mathcal{O}(n)$
- 空间复杂度：$\mathcal{O}(1)$
反转链表
迭代
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev, cur = None, head
while cur:
nxt = cur.next
cur.next = prev
prev = cur
cur = nxt
return prev
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *prev = nullptr, *cur = head;
while (cur) {
auto next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};
|
递归
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
rhs = self.reverseList(head.next)
head.next.next = head
head.next = None
return rhs
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
auto rhs = reverseList(head->next);
head->next->next = head;
head->next = nullptr;
return rhs;
}
};
|