代码随想录算法训练营第四天-24两两交换链表中的节点、19删除链表的倒数第N个节点、面试题02.07.链表相交、142环形链表II
1
2
| 24.05.16 初始记录
24.05.22 后两题的完成
|
初步题解
24 两两交换链表中的节点
题目链接：(https://leetcode.cn/problems/swap-nodes-in-pairs/description/)
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
|
public static LE707.ListNode swapPairs(LE707.ListNode head) {
while (head.next != null) {
LE707.ListNode temp = head.next.next;
head.next.next = head;
head.next = temp;
head = head.next.next;
}
return head;
}
public static LE707.ListNode swapPairs(LE707.ListNode head) {
LE707.ListNode dumyHead = new LE707.ListNode(-1);
dumyHead.next = head;
LE707.ListNode cur = dumyHead;
while (cur.next != null && cur.next.next != null) {
LE707.ListNode temp = cur.next.next.next;
LE707.ListNode node2 = cur.next.next;
LE707.ListNode node1 = cur.next;
cur.next = node2;
cur.next.next = node1;
cur.next.next.next = temp;
cur = node1;
}
return dumyHead.next;
}
|
19 删除链表的倒数第 N 个节点
题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
这道题直接看的解析。
面试题 02.07 链表相交
题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
提交是可以的，但是本地跑不行，看了一下可能是本地测试的 add 方法，每次都是新建一个对象，两个链表中的对象地址是不一致的，导致 tempA == tempB 这一步始终判断失败。
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
|
public static LE707.ListNode getIntersectionNode(LE707.ListNode headA, LE707.ListNode headB) {
int intersectVal = 0;
int skipA = 0;
int skipB = 0;
LE707.ListNode tempA = headA;
LE707.ListNode tempB = headB;
int sizeA = 0;
while (tempA != null) {
sizeA++;
tempA = tempA.next;
}
int sizeB = 0;
while (tempB != null) {
sizeB++;
tempB = tempB.next;
}
if (sizeA == 0 || sizeB == 0) {
return null;
}
tempA = headA;
tempB = headB;
if (sizeA >= sizeB) {
for (int i = 0; i < (sizeA - sizeB); i++) {
tempA = tempA.next;
skipA++;
}
} else {
for (int i = 0; i < (sizeB - sizeA); i++) {
tempB = tempB.next;
skipB++;
}
}
while (tempA != null) {
if (tempA == tempB) {
intersectVal = tempA.val;
return tempA;
}
tempA = tempA.next;
tempB = tempB.next;
skipA++;
skipB++;
}
return null;
}
|
142 环形链表 II
题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
不会，直接看的解析。
看讲解
24 两两交换链表中的节点
题目链接/文章讲解/视频讲解：：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html
这题看题解图会比较容易：
![image]()
看完根据这个图，总算是写出来了。
也还有别的方法（递归）：
1
2
3
4
5
6
7
8
9
10
11
12
13
| public ListNode swapPairs(ListNode head) {
if(head == null || head.next == null) return head;
ListNode next = head.next;
ListNode newNode = swapPairs(next.next);
next.next = head;
head.next = newNode;
return next;
}
|
注：将步骤二三互换，可以不定义 temp 节点。
19 删除链表的倒数第 N 个节点
题目链接/文章讲解/视频讲解：https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html
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
|
public static LE707.ListNode removeNthFromEnd(LE707.ListNode head, int n) {
LE707.ListNode dumyHead = new LE707.ListNode(-1);
dumyHead.next = head;
LE707.ListNode fast = dumyHead;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
LE707.ListNode slow = dumyHead;
while (fast != null && fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dumyHead.next;
}
|
步骤一：先移动快指针，快指针移动的位置与 n 相同。
步骤二：同时移动快慢指针，当快指针下一节点的位置为 0 时，此时慢指针指向的位置为要删除的节点的前一节点。
步骤三：删除指定节点。
注：为了避免多处理头节点的情况，添加虚拟头节点。
面试题 02.07 链表相交
题目链接/文章讲解：https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html
除了初步题解那种解法，还有一种，但是不是很能看懂理解，可以说第一次完全想不到，下面是解法和图解：
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/solutions/1190240/mian-shi-ti-0207-lian-biao-xiang-jiao-sh-b8hn/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA, p2 = headB;
while (p1 != p2) {
if (p1 == null) p1 = headB;
else p1 = p1.next;
if (p2 == null) p2 = headA;
else p2 = p2.next;
}
return p1;
}
|
142 环形链表 II
题目链接/文章讲解/视频讲解：https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html
![image]()
题解思路：
-
如何判断链表是否有环：首先这题使用快慢指针解法。如果无环，那么快指针到最后也不会与慢指针相遇；如果可以相遇，则说明有环。
-
快指针一定先进入环形，慢指针后进入环形。当慢指针进入环形时，就变成了追击问题，由快追击慢。因为指定快指针速度为 2 个节点，慢指针为 1 个节点，相对速度为 1 个节点，因此快慢一定会在环内相遇。
-
如图所示：假设相遇在点 P，入口在 start，三段路径分别如图所示，则此时 A 的行走路径为：x + n(y + z) + y，B 的行走路径为 x + y
-
又因为快指针速度为满指针的两倍，所以 x + n(y + z) + y = 2(x + y)，得出 x = n(y + z) - y，等式变形为 x = (n - 1)(y + z) + z，又 n >= 1。可以简化为，在相遇处，出发处各设一个指针，一起移动，两个指针一定会相遇。相遇处即为 start。
疑难点：
A：关键在当慢指针进入环形时，就变成了追击问题。也就是说，快指针的追击路线一定小于一圈，即追击时间一定不够慢指针跑满一圈。
A：因为指定快指针速度为 2 个节点，慢指针为 1 个节点，相对速度为 1 个节点，因此快慢一定会在环内相遇。（如果快指针的速度为 3，那就可能会跳过了）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public LE707.ListNode detectCycle(LE707.ListNode head) {
LE707.ListNode fast = head;
LE707.ListNode slow = head;
while (fast!= null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) {
LE707.ListNode index1 = head;
LE707.ListNode index2 = fast;
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
|
