【算法集訓】基礎數據結構：三、鏈表

鏈表就是將所有數據都用一個鏈子串起來，其中鏈表也有多種形式，包含單向鏈表、雙向鏈表等；
現在畢竟還是基礎階段，就先學習單鏈表吧；
鏈表用頭結點head表示一整個鏈表，每個鏈表的節點包含當前節點的值val和下一個節點next。
鏈表的好處就是刪除和插入比較容易，不需要移動其他元素。只需要改變下一個節點的指向值即可。

第一題面試題 02.02. 返回倒數第 k 個節點

https://leetcode.cn/problems/kth-node-from-end-of-list-lcci/description/
返回第k個節點的值，這里使用雙指針的思路，定義一個快指針和慢指針，兩個指針之間間隔k位，快指針移動到最后一個節點的下一個節點（即節點為空時）時就停止，此時慢指針對應的就是倒數第k個節點值。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/int kthToLast(struct ListNode* head, int k){struct ListNode * fast = head;struct ListNode * slow = head;for(int i = 0; i < k; ++i) {fast = fast->next;}while(fast) {fast = fast->next;slow = slow->next;}return slow->val;
}

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

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
刪除倒數第n個節點，思路和上一題一樣，先找到倒數第N個節點，我們要刪除這個節點，所以需要找到這個節點的前一個節點N+1；
直接將下一個值指向N的下一個值即可。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode * fast = head;struct ListNode * slow = head;for(int i = 0; i < n; ++i) {fast = fast->next;if(fast == NULL) {return head->next;}}fast = fast->next;while(fast) {fast = fast->next;slow = slow->next;}slow->next = slow->next->next;return head;}

第三題 206. 反轉鏈表

https://leetcode.cn/problems/reverse-linked-list/description/

第一種：迭代方法，定義一個當前節點cur和前一個節點pre，遍歷鏈表，將指向換一下方向即可，注意保存cur->next

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* reverseList(struct ListNode* head) {struct ListNode * pre = NULL;struct ListNode * cur = head;while(cur) {struct ListNode * temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;
}

第二種：遞歸
主要思想就是從最后一個開始，將它的指針指向前一個節點，然后前一個節點指向NULL；
這時又遞歸到前一個節點，和上面操作一樣，一直到第一個頭結點，這時頭結點會置為NULL；

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode * doReverse(struct ListNode * head, struct ListNode ** outHead) {遞歸臨界點，如果到最后一個節點則開始往回走；if(head == NULL || head->next == NULL) {*outHead = head;  outhead是最終翻轉后的頭結點，所以這里head最后一個節點就是outhead的頭結點return head;}
每次遞歸都向下一層，返回值為反轉后的struct ListNode * tail = doReverse(head->next, outHead);tail->next = head;head->next = NULL;return head;
}struct ListNode* reverseList(struct ListNode* head) {struct ListNode * outHead;doReverse(head, &outHead);return outHead;
}

第四題 237. 刪除鏈表中的節點

https://leetcode.cn/problems/delete-node-in-a-linked-list/description/
這道題代碼不難，主要的是思想，能不能想到這樣的方法。
只給了一個需要刪除的節點node，讓你刪除這個節點。
那么我們只需要將node->next的值賦值給node，那么這樣就可以刪除node->next，這樣同樣可以達到需要的結果。

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
void deleteNode(struct ListNode* node) {node->val = node->next->val;node->next = node->next->next;
}

第五題 24. 兩兩交換鏈表中的節點

https://leetcode.cn/problems/swap-nodes-in-pairs/description/
本題有兩種做法，迭代和遞歸，遞歸相對來說難理解。
一、遞歸

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* swapPairs(struct ListNode* head) {定義臨界點，即遞到最后一個節點或者空時開始歸。if(head == NULL || head->next == NULL) {return head;}這里就是記錄遞歸的當前節點和下一個節點，用于后續交換struct ListNode* now = head;struct ListNode* next = head->next;這里記錄的是后面已經完成交換的頭結點nextnext；struct ListNode* nextnext = swapPairs(now->next->next);這里算是核心，now->next = nextnext;  每次將當前節點的下個節點指向已經完成交換的頭結點next->next = now;  將當前節點下一個節點又指向當前節點，即完成本輪交換return 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* swapPairs(ListNode* head) {ListNode * virhead = new ListNode();virhead->next = head;ListNode * cur = virhead;while (cur->next != nullptr && cur->next->next != nullptr) {ListNode * temp1 = cur->next;ListNode * temp2 = cur->next->next->next;cur->next = cur->next->next;cur->next->next = temp1;cur->next->next->next = temp2;cur = cur->next->next;}return virhead->next;}
};