鏈表 I

237. Delete Node in a Linked List

206. Reverse Linked List

25. Reverse Nodes in k-Group

83. Remove Duplicates from Sorted List

鏈表操作常用技巧：

1. 能用遞歸解決盡量用遞歸
2. 雙指針fast, slow: fast一次向前走兩步, slow一次向前走一步
3. 在頭指針前面加入dummy指針

237. Delete Node in a Linked List

題意: 刪除鏈表中的某節點，被刪除的節點不會是尾節點

思路: 將需要刪除的節點的下個節點覆蓋刪除節點，然後改變刪除節點的指向為下下個節點

class Solution {public: void deleteNode(ListNode* node) { node->val = node->next->val; node->next = node->next->next; }};

206. Reverse Linked List

題意: 反轉鏈表(思路: 迭代或遞歸)

1 —> 2 -> 3 -> 4 -> 5 -> nullnull <- 1 <- 2 <- 3 <- 4 <- 5

迭代思路

1 —> 2 -> 3 -> 4 -> 5 -> null// op1 <- 2 -> 3 -> 4 -> 5 -> null1 <- 2 <- 3 -> 4 -> 5 -> null...

class Solution {public: ListNode* reverseList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* prev = nullptr; while (head->next) { ListNode* next = head->next; head->next = prev; prev = head; head = next; } head->next = prev; return head; }};

遞歸思路

1 —> 2 -> 3 -> 4 -> 5 -> null// op1 -> 2 <- 3 <- 4 <- 5null <- 1 <- 2 <- 3 <- 4 <- 5

class Solution {public: ListNode* reverseList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = nullptr; return newHead; }};

25. Reverse Nodes in k-Group

題意: 鏈表中相鄰k個元素構成一組，組內進行翻轉

1->2->3->4->5k = 2, return: 2->1->4->3->5k = 3, return: 3->2->1->4->5

思路: 遞歸

class Solution {public: ListNode* reverseKGroup(ListNode* head, int k) { ListNode* tail = head; int forward = k; while (forward-- && tail) tail = tail->next; if (tail == nullptr && forward >= 0) return head; ListNode* prev = nullptr, *cur = head; while (cur != tail) { ListNode* next = cur->next; cur->next = prev; prev = cur; cur = next; } head->next = reverseKGroup(tail, k); return prev; }};

83. Remove Duplicates from Sorted List

題意: 去除鏈表中重複的元素

思路: 找到第一個和當前元素不同的節點進行遞歸求解

class Solution {public: ListNode* deleteDuplicates(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* cur = head; while (cur && cur->val == head->val) cur = cur->next; head->next = deleteDuplicates(cur); return head; }};

推薦閱讀：