移除鏈表元素 && 設計鏈表
學會設置虛擬頭結點
翻轉鏈表
leetcode 206?https://leetcode.cn/problems/reverse-linked-list/description/
方法一：非遞歸+新開鏈表
頭插法：創建一個新的鏈表，遍歷舊鏈表，按順序在新鏈表使用頭插法分別插入元素。
方法二：非遞歸+不新開鏈表+從鏈表頭到鏈表尾翻轉
需要用臨時變量temp記錄下一個需要操作的節點，左邊那個尾pre，右邊那個是cur，到了cur是nullptr的時候結束。
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* temp;ListNode* cur = head;ListNode* pre = nullptr;while (cur) {temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}
};方法三：遞歸+不新開鏈表+從鏈表頭到鏈表尾翻轉
遞歸的過程實際上代替了方法二的pre = cur， cur = temp，其他都沒有區別。
class Solution {
public:ListNode* reverse(ListNode* pre, ListNode* cur) {if (cur == nullptr) {return pre;}ListNode* temp;temp = cur->next;cur->next = pre;return reverse(cur, temp);}ListNode* reverseList(ListNode* head) {return reverse(nullptr, head);}
};方法四：遞歸+不新開鏈表+從鏈表尾到鏈表頭翻轉
最后last取到了尾部元素，然后head這個時候是是到倒數第二個元素，倒轉指向然后接下來last就等于head，然后head等于last前面那個元素，以此類推直到最后。
class Solution {
public:ListNode* reverseList(ListNode* head) {if (head == nullptr) {return head;}if (head->next == nullptr){return head;}ListNode* last = reverseList(head->next);head->next->next = head;head->next = nullptr;return last;}
};兩兩交換鏈表中的節點
leetcode 24?https://leetcode.cn/problems/swap-nodes-in-pairs/description/
每次cur是需要操作的兩個節點的其中一個節點。cur->next->next不可以等于null，否則為奇數個節點，停止循環。每次記錄下cur->next和cur->next->next->next。操作順序及其步驟如下
class Solution {
public:ListNode* swapPairs(ListNode* head) {if (head == nullptr || head->next == nullptr) {return head;}ListNode* dummyhead = new ListNode();dummyhead->next = head;ListNode* cur = dummyhead;while (cur->next != nullptr && cur->next->next != nullptr) {ListNode* first = cur->next;ListNode* third = cur->next->next->next;cur->next = cur->next->next;cur->next->next = first;first->next = third;cur = cur->next->next;}ListNode* result = dummyhead->next;delete dummyhead;return result;}
};刪除鏈表的倒數第N個節點
使用快慢指針，快指針先走n步，然后快慢指針同時走，直到快指針下一個是null，在慢指針這個位置slow->next = slow->next->next。
鏈表相交
首先求出兩個鏈表的長度，求出二者之差為n，把長的鏈表頭指針移動n步，然后兩個頭指針同時移動，相等的時候中斷返回。
環形鏈表II
leetcode 142?https://leetcode.cn/problems/linked-list-cycle-ii/
這里主要涉及公式！
兩個要點
- 是否有環：此時因為快慢指針如果有環必定在環里面相遇，就看它們是否在快指針=nullptr之前相遇即可。
- 環形入口：快慢指針在一個點，此時取快指針（慢指針也可以），然后頭部一個指針同時移動，兩個指針移動速度均為一步一個節點。兩個節點相等之處就是環形入口。
class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* fast = head;ListNode* slow = head;while (fast && fast->next) {fast = fast->next->next;slow = slow->next;if (fast == slow) {ListNode* result = head;while (result != fast) {result = result->next;fast = fast->next;} return result;}}return nullptr;}
};
