链表 · C++技术

[TOC] ## 链表 ### 基本技能 * NULL异常处理 * dummy node哑巴节点 * 快慢指针 * 插入一个节点到排序链表 * 翻转链表 * 合并两个链表 * 找到链表的中间节点 ### 常见题型 #### [83. 删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/) 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次 ``` class Solution { public: ListNode* deleteDuplicates(ListNode* head) { ListNode* current = head; while (current) { while (current->next && current->next->val == current->val) { ListNode* rmNode = current->next; current->next = current->next->next; delete rmNode; } current = current->next; } return head; } }; ``` #### [82. 删除排序链表中的重复元素 II](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/) 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字 ``` class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head == NULL) return head; // 链表头也可能删除，所以用dummy node进行辅助 ListNode dummy(0); dummy.next = head; head = &dummy; while (head->next && head->next->next) { if (head->next->val == head->next->next->val) { int rmVal = head->next->val; while (head->next && head->next->val == rmVal) { ListNode* rmNode = head->next; head->next = head->next->next; delete rmNode; } } else head = head->next; } return dummy.next; } }; ``` #### [206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/) 翻转一个单链表 ``` class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* reverse = NULL; ListNode* next; while (head) { next = head->next; head->next = reverse; reverse = head; head = next; } return reverse; } }; ``` #### [92. 反转链表 II](https://leetcode-cn.com/problems/reverse-linked-list-ii/) 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明: 1 ≤ m ≤ n ≤ 链表长度。示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL ``` class Solution { public: /** * prev cur * | | * 1 -> 2 -> 3 -> 4 -> 5 -> NULL * * prev * |--------------------- cur * | | | * 1 4 -> 3 -> 2 -> NULL 5 */ ListNode* reverseBetween(ListNode* head, int m, int n) { ListNode dummy(0); dummy.next = head; ListNode* prev = &dummy; for (int i = 1; i < m; ++i) { prev = prev->next; } ListNode* cur = prev->next; ListNode* reverse = NULL; for (int i = m; i <= n; ++i) { ListNode* next = cur->next; cur->next = reverse; reverse = cur; cur = next; } prev->next->next = cur; prev->next = reverse; return dummy.next; } }; ``` #### [25\. K 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/) 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。 k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。解释的非常好：https://zhuanlan.zhihu.com/p/90170262 ```cpp class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { if (!head) return head; ListNode* a = head; ListNode* b = head; for (int i = 0; i < k; i++) { if (b == NULL) return head; b = b->next; } ListNode* newHead = reverse(a, b); a->next = reverseKGroup(b, k); return newHead; } ListNode* reverse(ListNode* a, ListNode* b) { ListNode* pre = NULL; ListNode* cur = a; while (cur != b) { ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } }; ``` #### [21\. 合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/) 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的 ``` class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* p = &dummy; while (l1 && l2) { if (l1->val < l2->val) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } p->next = l1 ? l1 : l2; return dummy.next; } }; ``` #### [86\. 分隔链表](https://leetcode-cn.com/problems/partition-list/) 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 ``` class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode smallerDummy(0); // 小于x的dummy ListNode biggerDummy(0); // 大于x的dummy ListNode* smaller = &smallerDummy; ListNode* bigger = &biggerDummy; while (head) { if (head->val < x) { smaller->next = head; smaller = smaller->next; } else { bigger->next = head; bigger = bigger->next; } head = head->next; } bigger->next = NULL; smaller->next = biggerDummy.next; return smallerDummy.next; } }; ``` #### [148\. 排序链表](https://leetcode-cn.com/problems/sort-list/) 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序思路：归并排序，找中点和合并操作 ``` class Solution { public: ListNode* sortList(ListNode* head) { if (head == NULL || head->next == NULL) return head; ListNode* mid = middle(head); ListNode* tail = sortList(mid->next); mid->next = NULL; head = sortList(head); return mergeList(head, tail); } ListNode* middle(ListNode* head) { ListNode* slow = head; ListNode* fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } ListNode* mergeList(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* p = &dummy; while (l1 && l2) { if (l1->val < l2->val) { p->next = l1; l1 = l1->next; } else { p->next = l2; l2 = l2->next; } p = p->next; } p->next = l1 ? l1 : l2; return dummy.next; } }; ``` #### [143\. 重排链表](https://leetcode-cn.com/problems/reorder-list/) 给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→… 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例 1: 给定链表 1->2->3->4, 重新排列为 1->4->2->3. ```cpp class Solution { public: void reorderList(ListNode* head) { if (head == NULL || head->next == NULL) return; ListNode* mid = middle(head); ListNode* tail = reverseList(mid->next); mid->next = NULL; ListNode dummy(0); ListNode* p = &dummy; bool isHead = true; //是否取head链表的节点 while (head && tail) { if (isHead) { p->next = head; head = head->next; } else { p->next = tail; tail = tail->next; } p = p->next; isHead = !isHead; // 取非，实现间或取值 } p->next = head ? head : tail; head = dummy.next; } ListNode* reverseList(ListNode* head) { ListNode* reverse = NULL; while (head) { ListNode* next = head->next; head->next = reverse; reverse = head; head = next; } return reverse; } ListNode* middle(ListNode* head) { ListNode* slow = head; ListNode* fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } }; ``` #### [141\. 环形链表](https://leetcode-cn.com/problems/linked-list-cycle/) 给定一个链表，判断链表中是否有环。 ``` class Solution { public: bool hasCycle(ListNode *head) { ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; } }; ``` #### [142\. 环形链表 II](https://leetcode-cn.com/problems/linked-list-cycle-ii/) [证明](https://zhuanlan.zhihu.com/p/33663488)：让两个指针其中一个从链表头 head 出发，一次走一步，让另一个指针从相遇点出发，也一次走一步，相遇点就是环的入口。 ```cpp class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* slow = head; ListNode* fast = head; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } // 无环 if (fast == NULL ||fast->next == NULL) return NULL; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } }; ``` #### [234\. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/) 请判断一个链表是否为回文链表 ```cpp class Solution { public: bool isPalindrome(ListNode* head) { if (head == NULL || head->next == NULL) return true; ListNode* mid = middle(head); ListNode* tail = reverseList(mid->next); mid->next = NULL; while (head && tail) { if (head->val != tail->val) return false; head = head->next; tail = tail->next; } return true; } ListNode* reverseList(ListNode* head) { ListNode* reverse = NULL; while (head) { ListNode* next = head->next; head->next = reverse; reverse = head; head = next; } return reverse; } ListNode* middle(ListNode* head) { // fast如果初始化为head->next则中点在slow->next // fast初始化为head，则中点在slow ListNode* slow = head; ListNode* fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; } }; ``` #### [138\. 复制带随机指针的链表](https://leetcode-cn.com/problems/copy-list-with-random-pointer/) 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的深拷贝。我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示： val：一个表示 Node.val 的整数。 random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。思路：1、hash 表存储指针，2、复制节点跟在原节点后面 ``` class Solution { public: Node* copyRandomList(Node* head) { if (head == NULL) return head; // 复制节点，紧挨到到后面 // 1->2->3 ==> 1->1'->2->2'->3->3' Node* p = head; while (p) { Node* node = new Node(p->val); node->next = p->next; p->next = node; p = node->next; } // 处理random指针 p = head; while (p) { if (p->random != NULL) p->next->random = p->random->next; p = p->next->next; } // 分离两个链表 Node dummy(0); Node* newList = &dummy; p = head; while (p) { newList->next = p->next; p->next = p->next->next; newList = newList->next; p = p->next; } // 原始链表头：head 1->2->3 // 克隆的链表头：newList 1'->2'->3' return dummy.next; } }; ``` #### [剑指 Offer 22. 链表中倒数第k个节点](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/) ```cpp class Solution { public: /** * 思路：分两路走，一路先走k步，然后同时走，先走的走到NULL节点，此时后走的就是所求 */ ListNode* getKthFromEnd(ListNode* head, int k) { // 先走k步 ListNode* ahead = head; for (int i = 0; i < k; ++i) { if (ahead == NULL) return NULL; ahead = ahead->next; } while (ahead) { ahead = ahead->next; head = head->next; } return head; } }; ``` ### 总结链表必须要掌握的一些点，通过上面的练习题，基本可以应付链表类的各种题目。