LeetCode題目鏈接
https://leetcode.cn/problems/swap-nodes-in-pairs/
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
https://leetcode.cn/problems/linked-list-cycle-ii/

題解
24.兩兩交換鏈表中的節點
可以模擬一下畫個圖，注意設立虛擬頭結點。

19.刪除鏈表的倒數第N個節點
注意要找到被刪除結點的前一個結點（這道題也是被提示這個思路才做出來的）。

面試題02.07.鏈表相交
啟發思路：先求出兩個鏈表長度，再求長度的差值，讓長鏈表的指針移動到與短鏈表剩余長度相同的位置。
注意此題只能在leetcode上跑出正確結果，本地IDE運行時兩個鏈表是單獨建成不相交，所以無結果，下面附著的代碼是本地代碼。

142.環形鏈表II
拿到題目第一反應，開一個10的4次方的數組，作為判定鏈表中結點值是否出現過的判定（假定題目給的鏈表結點沒有重復的，有重復的就不行了），如果當前結點的next結點的值顯示為判定過，則鏈表存在環。
看了題解，采用快慢指針法。
本題根據題解，有兩個地方需要注意，一是快慢指針遍歷時的循環條件，我在代碼里注釋掉的是我自己寫的，此時當結點只有一個時就會報錯，因為快指針不存在下一個結點的next，下一個結點已然是NULL，因此在循環遍歷時是判斷快指針的存在與否與快指針的下一個結點存在與否；二是根據題解用數學方法求出環入口的位置，這段代碼的循環要放在第一個循環里面，因為只有在第一個循環中發現有環后才能再尋找環入口。代碼很簡潔，重要的是思想。

代碼

//24.兩兩交換鏈表中的節點
#include <iostream>
#include <vector>
using namespace std;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) {if (head == NULL) return NULL;ListNode* pre1 = new ListNode;pre1->next = head;ListNode* pre2 = head;ListNode* pre3 = pre1;while (pre1!= NULL && pre2!= NULL && pre1->next != NULL && pre2->next != NULL) {int tmp = pre2->next->val;pre2->next->val = pre1->next->val;pre1->next->val = tmp;pre1 = pre1->next->next;pre2 = pre2->next->next;}return pre3->next;}
};ListNode* createList(vector<int> nums) {if (nums.size() == 0) return NULL;ListNode* cur = new ListNode(nums[0]);cur->next = NULL;ListNode* pre = cur;int len = 1;while (len < nums.size()) {cur->next = new ListNode(nums[len]);cur = cur->next;len++;}return pre;
}int main() {Solution s;vector<int> nums = { 1, 2, 3, 4, 5 };ListNode* node = createList(nums);ListNode* tmp = node;while (tmp != NULL) {printf("%d ", tmp->val);tmp = tmp->next;}printf("\n");node = s.swapPairs(node);while (node != NULL) {printf("%d ", node->val);node = node->next;}return 0;
}

//19.刪除鏈表的倒數第N個節點
#include <iostream>
#include <vector>
using namespace std;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) {}
};ListNode* createList(vector<int>nums) {ListNode* cur = new ListNode(nums[0]);ListNode* pre = cur;int len = 1;while (len < nums.size()) {cur->next = new ListNode(nums[len]);cur = cur->next;len++;}return pre;
}class Solution {
public:int getListLen(ListNode* head) {int len = 0;while (head) {len++;head = head->next;}return len;}ListNode* removeNthFromEnd(ListNode* head, int n) {int len = getListLen(head);int num = len - n;ListNode* pre = new ListNode;pre->next = head;ListNode* pre2 = pre;while (num--) {pre = pre->next;}pre->next = pre->next->next;return pre2->next;}
};int main() {vector<int> nums = { 1,2 };ListNode* node = createList(nums);ListNode* tmp = node;while (tmp) {printf("%d ", tmp->val);tmp = tmp->next;}printf("\n");Solution s;node = s.removeNthFromEnd(node, 1);while (node) {printf("%d ", node->val);node = node->next;}return 0;
}

//面試題02.07.鏈表相交
#include <iostream>
#include <vector>
using namespace std;struct ListNode {int val;ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};ListNode* createList(vector<int> nums) {if (nums.size() == 0) return NULL;ListNode* cur = new ListNode(nums[0]);ListNode* pre = cur;int len = 1;while (len < nums.size()) {cur->next = new ListNode(nums[len]);cur = cur->next;len++;}return pre;
}class Solution {
public:int getListLen(ListNode* head) {int len = 0;while (head) {len++;head = head->next;}return len;}ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {int lenA = getListLen(headA), lenB = getListLen(headB);if (lenA < lenB) {ListNode* tmp = headA;headA = headB;headB = tmp;}int diff = abs(lenA - lenB);while (diff) {headA = headA->next;diff--;}while (headA && headB) {if (headA == headB) return headA;headA = headA->next;headB = headB->next;}return NULL;}
};int main() {vector<int> nums1 = { 4,1,8,4,5 }, nums2 = { 5,0,1,8,4,5 };ListNode* headA = createList(nums1);ListNode* headB = createList(nums2);Solution s;ListNode* node = s.getIntersectionNode(headA, headB);ListNode* tmp = headA;while (tmp) {printf("%d ", tmp->val);tmp = tmp->next;}printf("\n");tmp = headB;while (tmp) {printf("%d ", tmp->val);tmp = tmp->next;}printf("\n");while (node) {printf("%d ", node->val);node = node->next;}return 0;
}

//142.環形鏈表II
class Solution {
public:ListNode* detectCycle(ListNode* head) {ListNode* slow = head, *fast = head;//do {while (fast && fast->next) {slow = slow->next;fast = fast->next->next;//} while (slow != fast && slow && fast);if (slow == fast) {ListNode* index1 = head, * index2 = slow;while (index1 != index2) {index1 = index1->next;index2 = index2->next;}return index1;}}return NULL;}
};