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

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

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

学习前的想法

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

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

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

思路图

建议参考我的一下代码来理解这张图（图画的不好见谅🤪）：

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
后续会补充