兩兩交換鏈表中的節點

/*** 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);dummyHead->next = head;ListNode *cur = dummyHead; while(cur->next&&cur->next->next){ListNode* tmp = cur->next; // 記錄臨時節點ListNode* tmp1 = cur->next->next->next; // 記錄臨時節點cur->next = cur->next->next;    // 步驟一cur->next->next = tmp;          // 步驟二cur->next->next->next = tmp1;   // 步驟三cur = cur->next->next; // cur移動兩位，準備下一輪交換}return  dummyHead->next;}
};

刪除鏈表的倒數第N個節點

注意使用虛擬頭節點，可以避免對頭節點的判斷，防止各種復雜情況

/*** 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);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n--&&fast){fast = fast->next;}fast = fast->next;while(fast){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummyHead->next;}
};

/*** 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);dummyHead->next = head;ListNode* slow = dummyHead;ListNode* fast = dummyHead;while(n--&&fast){fast = fast->next;}fast = fast->next;while(fast){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummyHead->next;}
};

if(head->next==nullptr)return nullptr;ListNode* slow = head;ListNode* fast = head;while(n--&&fast!=nullptr){fast = fast->next;}fast = fast->next;while(fast){slow = slow->next;fast = fast->next;}slow->next= slow->next->next;return head;

鏈表相交

代碼隨想錄

面試題 02.07. 鏈表相交 - 力扣（LeetCode）

v1.0：感覺使用了虛擬頭節點之后很順利，直接模擬就可以寫出來，不過就是感覺寫的有點長？
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *dummyHeadA = new ListNode(0);ListNode *dummyHeadB = new ListNode(0);int lengthA = 0, lengthB = 0;dummyHeadA->next = headA;dummyHeadB->next = headB;ListNode *lna = dummyHeadA;ListNode *lnb = dummyHeadB;while(lna){lengthA++;lna = lna->next;}while(lnb){lengthB++;lnb = lnb->next;}int steps = 0;lna = dummyHeadA;lnb = dummyHeadB;if(lengthA>=lengthB){steps = lengthA - lengthB;while(steps--){lna = lna->next;}while(lna->next!=lnb->next){lna = lna->next;lnb = lnb->next;}if(lna->next==nullptr){return nullptr;}else{return lna->next;}}else{steps = lengthB - lengthA;while(steps--){lnb = lnb->next;}while(lna->next!=lnb->next){lna = lna->next;lnb = lnb->next;}if(lna->next==nullptr){return nullptr;}else{return lna->next;}}}
};

環形鏈表Ⅱ

142. 環形鏈表 II - 力扣（LeetCode）

v1.0 這道題很巧妙，是看了隨想錄的講解才做出來的
1. 判斷有無環:定義快慢指針，快指針一次走兩個節點，慢指針走一個，快指針追上慢指針說明有環
2. 追上時需要紙筆列下式子，此時快慢指針走過的節點數量，然后要求的是從開始節點到進入環的節點的長度
3. 具體推導可以看隨想錄，總之就是需要列一下式子就可以找出關系了~
/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *dummyHead = new ListNode(0);dummyHead->next = head;ListNode *fast = head;ListNode *slow = head;ListNode *aux = head;while(fast&&fast->next){fast= fast->next->next;slow = slow->next;if(fast==slow){while(aux!=slow){slow=slow->next;aux=aux->next;}return aux;}}return nullptr;}
};