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)

代碼

更更更