?24. 兩兩交換鏈表中的節點

① 使用虛擬節點

② 最后返回頭結點的時候，head 本來的頭節點已經和第二位交換了，需要重新賦值

③ 使用臨時指針保存變量

④ 如果是空的不用特殊判斷，空的返回頭節點也還是空的

class Solution {
public:ListNode* swapPairs(ListNode* head) {ListNode* dummyHead = new ListNode(0);dummyHead->next = head;ListNode* cur = dummyHead;while(cur->next != nullptr && cur->next->next != nullptr){ListNode* tmp = cur->next;ListNode* tmp1 = cur->next->next->next;cur->next = cur->next->next;cur->next->next = tmp;tmp->next = tmp1;cur = cur->next->next;}head = dummyHead->next;return head;}
};

19. 刪除鏈表的倒數第 N 個結點

① 快慢指針，先讓 fast 走 n 步，快指針和慢指針之間相差 n，然后兩個指針同時走，fast 走到最后的時候，slow 就是倒數第 n 個

②fast 走了 n 以后，要再向前走一個，因為刪除的時候，slow 需要指到刪除節點的前一個

③ 使用虛擬頭節點會更方便

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {//虛擬頭節點ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* fast = dummy;ListNode* slow = dummy;//fast先走n步while(n-- && fast != nullptr){fast = fast->next;}//fast多走一步，這樣slow就可以指向刪除節點的上一個節點fast = fast->next;while(fast != nullptr){fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return dummy->next;}
};

面試題 02.07. 鏈表相交

① 先計算鏈表長度然后使兩個鏈表末尾對齊，再讓指針走到同一個長度位置，開始逐一對比后邊的節點是否是一樣的

② 要考慮哪個鏈表更長的問題

③ 讓長的鏈表的指針走到短的鏈表頭節點位置的時候，走的是鏈表差值不是鏈表長度

④ 第一次計算鏈表長度的時候，最后指針記得要回頭節點的位置

/*** 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* cur1 = headA;ListNode* cur2 = headB;int lenA = 0;int lenB = 0;//計算鏈表長度while(cur1 != nullptr){lenA++;cur1 = cur1->next;}while(cur2 != nullptr){lenB++;cur2 = cur2->next;}cur1 = headA;cur2 = headB;//末尾對其if(lenA>lenB){for(int i=0; i<lenA - lenB;i++){cur1 = cur1->next;}}else{for(int i=0; i<lenB - lenA;i++){cur2 = cur2->next;}}while(cur1 != nullptr && cur2 != nullptr){if(cur1 == cur2){return cur1;}cur1 = cur1->next;  // 移動cur1cur2 = cur2->next;  // 移動cur2}return NULL;}
};