leetcode_day4

本文最后更新于 2024年5月31日 下午

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

​ 链表貌似就是虚头+双指针+遍历,回到老家的感觉,注意对空节点的检查就好,题不难

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
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode * virhead = new ListNode();
if(head == nullptr || head->next == nullptr) return head;
virhead->next = head;
ListNode * left = virhead;
ListNode * right = head;
while(right && right->next) {
left->next = right->next;
right->next = right->next->next;
left->next->next = right;
left = right;
right = right->next;
}
return virhead->next;
}
};

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

算脑筋急转弯吧,不过之前做过,已经没有难度了,思路就是让fast先走n步,再和slow一起走,这样fast走到最后slow就是倒数第n个了。

​评论区在diss官解的“一次遍历”说法,去搜了一下,看见了宫水三叶前辈的帖,下为结论:

我们应该用「对数组的访问次数」来定义遍历多少次,而不是「利用 for 循环的个数」来定义。 上述无论那种方法,对数组访问次数都是一样的。

出处:为什么「一次遍历」要比「两次遍历」慢 (含小实验代码) | Java 刷题打卡-阿里云开发者社区 (aliyun.com)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode * vir = new ListNode();
vir->next = head;
ListNode * fast = vir;
ListNode * slow = vir;
for(int i = 0;i < n;i++) {
fast = fast->next;
}
while(fast && fast->next) {
slow = slow->next;
fast = fast->next;
}
ListNode * t = slow->next;
slow->next = slow->next->next;
delete t;
return vir->next;
}
};

链表相交

思路比较原始,都走一遍,把屁股对齐,长的先走几步把优势消耗,然后一起走找交点。

官解的追及思路更优雅,不过复杂度相同。官解

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
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode * vir = new ListNode();
vir->next = head;
ListNode * fast = vir;
ListNode * slow = vir;
for(int i = 0;i < n;i++) {
fast = fast->next;
}
while(fast && fast->next) {
slow = slow->next;
fast = fast->next;
}
ListNode * t = slow->next;
slow->next = slow->next->next;
delete t;
return vir->next;
}
};

环形链表II

数学题,刚开始没推出来,注意把环分成走过的b段和没走过的c段,这样就很直观了,贴个图帮助理解

环形链表示意图

公式中a对应图中x,y对应b,z对应c

求的是a,slow被碰到时离入口还差c,所以此时再来个指针从头开始一起走,碰到的时候刚好就是等式两边,即入口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode * fast = head;
ListNode * slow = head;
while(fast) {
slow = slow->next;
if(!fast->next) return nullptr;
fast = fast->next->next;
if(fast == slow) {
ListNode * ans = head;
while(ans != slow) {
ans = ans->next;
slow = slow->next;
}
return ans;
}
}
return nullptr;
}
};

不太难,链表问题不大,注意空指针检查就行。


leetcode_day4
https://novelyear.github.io/2024/05/30/leetcode-day4/
作者
Leoo Yann
更新于
2024年5月31日
许可协议