我们专门开个链表的算法题坑，方便总结在笔面试中可能会涉及到的链表操作。
在ACM中我们都用数组模拟双向链表，所以就不要嘲笑为什么我一个ACMer还要整理力扣的题了，是真不会啊。
求两个单向链表的相交点
力扣链接
一般链表的题，输入只给你一个指向链表头的头指针。但是这题我们要求两个单向链表的相交点，所以我们开始有两个头指针 headA 和 headB。
怎么求相交点呢？或许可以枚举第一个链表上的每个点，然后遍历第二个链表的每个点，看看二者是否有相同的地址。这种显然是 O(n2) 的。
有没有更简单的解法呢？假设我们目标是想出一个 O(n) 的解法，那么似乎我们遍历一次链表就 O(n) 了。
遍历完了然后呢？假设我们此时从另一个链表重新开始遍历，会发生什么？
假设链表A和链表B有共同后缀长度 z，而A的前缀长度为 x，B为 y，那么我们同时从头遍历链表 A 和 B，若到头了就从另一个链表重新开始遍历。
那么你会惊讶地发现，当我们这么遍历 x + y + z 步后，二者所在的点就是交互点！
也就是说，如果我们直接按照“遍历完当前链表就换链表遍历”的想法遍历，就一定会在某个时刻，二者会到一个点上，而这个点就是我们要的相交点。
而且我们必然在第二次换链表遍历（即换回来原来链表开始遍历）之前得到该相交点。如果没有的话，说明二者无相交。
1
2
3
4
5
6
7
8
9
10
| ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* A{headA};
ListNode* B{headB};
while(A != B)
{
A = A ? A->next : headB;
B = B ? B->next : headA;
}
return A;
}
|
反转链表
力扣链接
这个很简单，我们在遍历的时候改一改指针就行了。记录当前指针 p 和当前指针下一位 q，将 q 的指针指向 p 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| ListNode* reverseList(ListNode* head) {
if(!head) return head;
ListNode* p{head};
ListNode* q{head->next};
while(q)
{
ListNode* tmp{q->next};
q->next = p;
p = q;
q = tmp;
}
head->next = nullptr;
return p;
}
|
判断一个链表是否是回文的
力扣链接
简单，直接把值记到一个数组内然后判回文
时间复杂度显然限制死 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
| bool isPalindrome(ListNode* head) {
ListNode* slow{head};
ListNode* fast{head};
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
ListNode* q = reverseList(slow);
bool pd{true};
ListNode* p{head};
while(p && q && pd)
{
if(p->val != q->val)
{
pd = false;
break;
}
p = p->next;
q = q->next;
}
return pd;
}
|
环形链表
力扣链接
判断链表是否有环。
同样用快慢节点。很容易可以算出，如果有环，那么在经过了环的长度的时间（实际上这是上界，可能也是环的长度除以二、除以三等等）后，二者会相遇。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| bool hasCycle(ListNode *head) {
if(!head) return false;
ListNode* slow{head};
ListNode* fast{head};
bool pd{};
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
pd = true;
break;
}
}
return pd;
}
|
环形链表找第一个节点
力扣链接
上个题的升级版，在判断有无环的基础上要求找第一个节点。
上个题我们知道，slow节点第一次进入环内会和fast在环内旋转若干遍发生第一次接触。
假设用时 t 步，fast旋转了 k 遍，环前长度 x ，第一次接触到环前长度为 y，剩余长度为 z，那么可以分别得出slow节点和fast节点经过的距离。slow走了 t = x + y，fast走了 2t = x + k(y + z) + y，可以算出 x = (k − 1)y + kz。
也就是说 x 等于走了 k − 1 遍环加上 z，而slow节点在环的第 y 个节点相遇，如果让其再走 x 步刚好能够走完 k 遍环。然而我们并不知道 x，因此可以再搞个slow2节点从head开始，和slow一起走，二者相遇的地方就是我们要求的环的第一个节点。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| ListNode *detectCycle(ListNode *head) {
ListNode* slow = head, *fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast) break;
}
if(!fast || !fast->next) return nullptr;
ListNode* slow2 = head;
while(slow2 != slow)
{
slow = slow->next;
slow2 = slow2->next;
}
return slow;
}
|
合并两个有序链表
力扣链接
记三个指针，分别是 p, q, now。然后模拟即可。
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
| ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *p = list1, *q = list2;
if(!p) return q;
if(!q) return p;
ListNode *now, *ret;
if(p->val < q->val)
{
now = ret = p; p = p->next;
}
else
{
now = ret = q; q = q->next;
}
while(p && q)
{
if(p->val < q->val)
{
now->next = p;
now = p;
p = p->next;
}
else
{
now->next = q;
now = q;
q = q->next;
}
}
if(p) now->next = p;
if(q) now->next = q;
return ret;
}
|
链表高精度相加
力扣链接
没啥好说的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carry{};
ListNode *head = nullptr, *p = nullptr;
while(l1 || l2 || carry)
{
if(l1) carry += l1->val, l1 = l1->next;
if(l2) carry += l2->val, l2 = l2->next;
ListNode* fuck = new ListNode(carry % 10);
carry /= 10;
if(!head) head = p = fuck;
else p->next = fuck, p = fuck;
}
return head;
}
|
删除链表倒数第n个节点
先搞个指针走 n 步，然后一起走。注意判头节点被删的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *p = head, *q = head, *pre = nullptr;
for(int i = 0; i < n; ++i)
{
q = q->next;
}
while(q)
{
q = q->next;
pre = p;
p = p->next;
}
if(pre && pre->next)
{
pre->next = pre->next->next;
}
if(!pre) return head->next;
return head;
}
|
两两交换链表中的节点
力扣链接
四个四个模拟
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| ListNode* swapPairs(ListNode* head) {
if(!head) return head;
ListNode* ret = head;
if(head->next) ret = head->next;
ListNode *a = head, *b = head->next;
while(b)
{
ListNode *c = b->next;
b->next = a;
if(!c) {a->next = nullptr; break;}
if(c->next) a->next = c->next;
else a->next = c;
a = c;
b = c->next;
}
return ret;
}
|
K 个一组翻转链表
力扣链接
翻转后处理前后指针即可
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
| class Solution {
pair<ListNode*, ListNode*> reverse(ListNode *p, ListNode *q)
{
ListNode *pre = nullptr;
ListNode *tail = p;
while(p != q)
{
ListNode *tmp = p->next;
p->next = pre;
pre = p;
p = tmp;
}
p->next = pre;
return make_pair(q, tail);
}
public:
ListNode* reverseKGroup(ListNode* head, int k) {
ListNode dummy(114, head);
ListNode *p = head;
ListNode *pre = &dummy;
while(p)
{
for(int i = 0; i < k - 1; ++i)
{
p = p->next;
if(!p) return dummy.next;
}
ListNode *nxt = p->next;
pair<ListNode*, ListNode*> pp = reverse(pre->next, p);
pre->next = pp.first;
(pp.second)->next = nxt;
pre = pp.second;
p = nxt;
}
return dummy.next;
}
};
|
