代码随想录-DAY④-链表——leetcode 24 | 19 | 142

24

思路

如果 pre 的后面没有节点或者只有一个节点，则没有更多的节点需要交换,

否则，通过更新节点的指针关系交换 pre 后面的两个节点，

最后，返回新的链表的头节点 dummyhead->next。

• 时间复杂度：O(n)

• 空间复杂度：O(1)

代码

/*** 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 *dummyhead = new ListNode(0, head);ListNode *pre = dummyhead, *cur = head, *ahead;while(pre->next!=nullptr && pre->next->next!=nullptr){ahead = cur->next;cur->next = ahead->next;ahead->next = cur;pre->next = ahead;pre = cur;cur = cur->next;}ListNode* ans = dummyhead->next;delete dummyhead;return ans;}
};

19

思路

让 fast 先移动n步，然后让 fast 和 slow 同时移动，

直到 fast 指向链表末尾，删掉slow所指向的节点。

使用虚拟头结点，方便处理删除实际头结点的逻辑，

注意空间清理。

• 时间复杂度：O(n)

• 空间复杂度：O(1)

代码

/*** 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 *dummyhead = new ListNode(0, head);ListNode *fast=head, *slow=dummyhead, *temp, *ans;while(n--){fast=fast->next;}while(fast!=nullptr){fast=fast->next;slow=slow->next;}temp=slow->next;slow->next=slow->next->next;ans = dummyhead->next;delete temp;delete dummyhead;return ans;}
};

142

思路

设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。

根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 2 倍。

因此，我们有 a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)
有了 a=c+(n−1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

详见官方题解：

. - 力扣（LeetCode）

时间复杂度：O(N)

空间复杂度：O(1)

代码

更更更