代码随想录算法训练营第四天| 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II 、总结

24. 两两交换链表中的节点

题目链接:24. 两两交换链表中的节点
文档讲解:24. 两两交换链表中的节点
视频讲解:帮你把链表细节学清楚! | LeetCode:24. 两两交换链表中的节点
目标:
状态:独立使用虚拟头节点AC

学习前的想法

在第三天的学习中,我学习了虚拟头节点的使用,本题的目的是将链表中的节点两两交换。

根据题目的图示可以知道,题目只要求了交换刚开始的相邻节点,即假设有四个元素a, b, c, d,我们只需交换abcd即可。(当然想要完成每个元素和其后一个于元素交换也能很轻松的实现,只需修改一行代码😼)

使用虚拟头节点,并声明两个指针用来存储位置信息,具体思路如下图所示:

思路图

建议参考我的一下代码来理解这张图(图画的不好见谅🤪):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode *dummyHead = new ListNode(0, head);
ListNode *cur = dummyHead;

while(cur->next != nullptr && cur->next->next != nullptr) {
ListNode *p = cur->next;
cur->next = cur->next->next;
p->next = cur->next->next;
cur->next->next = p;
// 在这里如果为cur = cur->next,则可以完成
// 每个元素和后一个元素相交换的任务
cur = cur->next->next;
}

return dummyHead->next;
}
};

2024/2/24
没想到能够独立使用虚拟头节点完成题目,看来还是学会了一些东西的🤭

学习后的想法

再次提醒自己,使用虚拟头节点的优点是可以统一对头节点和普通节点的操作,不需要再对其进行判断。

我上面的思路和卡哥基本一致,但是上面思路细节方面可能没说清楚,下面我将会跟着卡哥的讲解理一遍思路:

我们需要操作两个节点,就需要把当前指针cur指向这两个节点之前的一个节点,正如我上面先将cur指向了虚拟节点,即 将操作指针指向需要反转的两个节点的前一个结点。

实现

1
2
3
4
5
6
7
8
9
10
11
12
dummyHead->next = head;
cur = dummyHead; // 这样才能操作后两个节点
while(cur->next != nullptr && cur->next->next != nullptr) {
tmp = cur->next; // 注意在这里是存储节点
// 这一步其实没必要,改变一下操作顺序就行
// 建议参考我上面的代码🤭
tmp2 = cur->next->next->next;
cur->next -cur->next->next;
cur->next->next = tmp;
tmp->next = tmp2;
cur = cur->next->next;
}

19.删除链表的倒数第N个节点

题目链接:19.删除链表的倒数第N个节点
文档讲解:19.删除链表的倒数第N个节点
视频讲解:链表遍历学清楚! | LeetCode:19.删除链表倒数第N个节点
目标:
状态:没想到啊,没想到😶

学习前的想法

这一题卡哥提示使用双指针,并指出了注意事项需要删除第N个节点时,遍历指针需要指向这个节点的前一个节点

题目要求删除链表的倒数第n个节点,之后返回链表的头节点。

我的第一想法是先获取链表的长度,然后计算出倒数第n个是正数第几个节点。

这样的话需要进行一次判断,删除的是头节点还是普通节点。

尝试实现代码如下:

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* removeNthFromEnd(ListNode* head, int n) {
int count = 1;
ListNode *cur = head;

while(cur != nullptr) {
cur = cur->next;
count++;
}

if(count == n) return head->next;

cur = head;
int tmp = count - n - 1;

while(tmp--) cur = cur->next;

cur->next = cur->next->next;

return head;
}
};

代码报错空指针异常.

2024/2/24
why!!!!!!

学习后的想法

删除某个节点,操作指针需要指向其前一个结点。

使用虚拟头节点,定义一个快指针,一个慢指针,初始时均指向虚拟头节点。

如何获取倒数第n个节点?

先让快指针向后移动n步,则此时快慢指针之间的距离为n,当快指针指向null时,慢指针刚好指向倒数第n和节点。

2024/2/24
这个思路确实牛逼🤩

因此,我们获取需要删除节点的前一个节点,则只需将快指针先向后移动n + 1步,此时慢指针的位置刚刚好。

实现

1
2
3
4
5
6
7
8
9
10
11
dummyHead->next = head
dummyHead = slow = fast
n++ // 走n+1步
while(n-- && fast != nullptr) fast = fast->next;
while(fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
// 记得要释放空间
slow->next = slow->next->next;
return dummyHead->next;

面试题 02.07. 链表相交

题目链接:面试题 02.07. 链表相交
文档讲解:面试题 02.07. 链表相交
视频讲解:
目标:
状态:没想到

学习前的想法

题目要求返回两个单链表相交的起始节点,相交即两个单链表的节点中含有公共地址。有以下几个问题需要考虑:

如何判断节点是否为公共节点?

由于两个链表长度可能不一致,如何将所有的地址比较完毕?

学习后的想法

若两链表相交,则交点指针相等。

解决长度问题的办法是将长链表的指针向后移动,知道其剩余长度等于短链表的长度。

因此我们首先需获取长短链表的长度,并求出两个链表的长度差,使两链表末尾对齐,指针位置对齐,之后向后遍历,知道指针相等或为空。

实现

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
curA = headA, curB = headB;
lenA = 0, lenB = 0;

while(curA != nullptr) {
lenA++;
curA = curA->next;
}

while(curB != nullptr) {
lenB++;
curB = curB->next;
}

// 注意这里要及时的将俩个指针置为头指针
curA = headA, curB = curB;

// 交换AB各项取值,保证A始终为长链表,方便后续统一操作
if(lenB > lenA) swap(A, B);

int gap = lenA - lenB;
while(gap--) curA = curA->next;

while(curA != nullptr) {
if(curA = curB) return curA;
curA = curA->next;
curB = curN->next;
}

return NULL;

142.环形链表II

题目链接:142.环形链表II
文档讲解:142.环形链表II
视频讲解:142.环形链表II
目标:
状态:不会。。。是真的绷不住这个数学推理,根本想不到🤗

学习前的想法

这道题目需要去寻找第一个开始循环的节点,找到则返回该节点位置,找不到则返回null

首先返回null的逻辑很好想,只需使用一个while循环,当指针为空时退出,此时表明链表无环。

之后便是如何寻找环的初始位置,这个并没有想出如何寻找。

尝试实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *dummyHead = new ListNode(0, head);
ListNode *cur = dummyHead;

while(cur != nullptr) {
cur = cur->next;
}

return NULL;
}
};

2024/2/24
只写出了一个退出循环的逻辑😂,不过也不知道对不对

学习后的想法

如何判断一个链表是否有环?

双指针,一个快指针,一个慢指针,如果相遇则有环

实现细节:快指针每次走两个节点,慢指针每次走一个节点,相遇则有环。

为什么注定相遇?

快指针相对于慢指针,以每次一个节点的速度去追逐

如何找到环的入口?

这是一个数学问题,先给出结论:

头节点到环的入口的距离,等于环中快慢指针相遇的节点到换入口的距离,分别使用两个指针遍历,则两个指针相遇的节点就是环的入口。

2024/2/24
证明过程较为复杂,后续会补上

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fast = head, slow = head;

while(fast != null && fast->next != null) {
fast = fast->next->next;
slow = slow->next;

if(fast == slow) {
index1 = fast;
index2 = head;

while(index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}

return index1;
}
}
return null;

收获与学习时长

学习时长: 3h 7min

收获

熟悉了双指针,虚拟头节点的使用。

学会了如何获取倒数第n个元素

学会了如何判断环形链表,以及如何获取环的入口节点

总结

学完链表后至少需要熟悉一下几种常用的方法:

双指针法:快慢指针、左右指针

虚拟头节点

一些常用的技巧

2024/2/24
后续会补充