链表
删除链表中的某个节点或某一段区间
leetcode.203
- 链接https://leetcode.cn/problems/...
- 解题办法：链表中删除一个节点的惯例办法就是找到这个节点的前驱节点，将前驱节点的next指针指向以后节点的后继节点
leetcode解题代码
/** * 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* removeElements(ListNode* head, int val) { auto dummy = new ListNode(-1); dummy->next = head; for (auto p = dummy; p; p = p->next){ auto q = p->next; while (q && q->val == val) q = q->next; p->next = q; } return dummy->next; }};
leetcode.19
- 链接https://leetcode.cn/problems/...
- 解题办法：与上一题相似，须要先求出链表总长度，再找到以后节点的前驱节点
留神：以后节点的前驱节点为倒数第n+1个点，即为负数第len-n个点
须要挪动len-n-1次挪动到前驱节点 leetcode解题代码
/** * 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* removeNthFromEnd(ListNode* head, int n) { auto dummy = new ListNode(-1); dummy->next = head; int len = 0; for (auto p = dummy; p; p = p->next) len ++; auto p = dummy; for (int i = 0; i < len - n - 1; i ++) p = p->next; p->next = p->next->next; return dummy->next; }};
leetcode.237
- 链接https://leetcode.cn/problems/...
- 解题办法：本题不是惯例意义上的删除节点，无奈像上一道题一样找到以后节点的前驱节点
本题的办法比拟取巧，即先把后继节点的值赋值给以后节点，而后再删除后继节点 leetcode解题代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: void deleteNode(ListNode* node) { node->val = node->next->val; node->next = node->next->next; }};
leetcode.2095
- 链接https://leetcode.cn/problems/...
- 解题办法：快慢指针
快指针每次向前挪动两位，慢指针每次向前挪动一位
当快指针走到链表结尾，满指针刚好指向链表两头
通过虚构头节点让快慢指针都回退一位，满指针则刚好指向两头节点的前驱节点 leetcode解题代码
/** * 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* deleteMiddle(ListNode* head) { auto dummy = new ListNode(-1); dummy->next = head; auto fast = dummy, slow = dummy; while (fast && fast->next && fast->next->next){ fast = fast->next->next; slow = slow->next; } slow->next = slow->next->next; return dummy->next; }};
leetcode.83
- 链接https://leetcode.cn/problems/...
- 解题办法：双指针
cur指针指向无反复元素链表的最初一个节点
p指针遍历链表，如果p指针元素和cur指针元素不相等则将cur指针指向p，并更新cur指针
最初cur指针是无反复元素链表的最初一个节点，记得将其指向空 leetcode解题代码
/** * 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* deleteDuplicates(ListNode* head) { if (!head) return head; auto cur = head; for (auto p = head->next; p; p = p->next) if (p->val != cur->val) cur = cur->next = p; cur->next = nullptr; return head; }};
leetcode.82
- 链接https://leetcode.cn/problems/...
- 解题办法：双指针
p指针保护新链表的最初一位，q指针遍历去找无反复元素的区间
如果区间长度=1则阐明没有反复元素，保留
如果区间长度>1则阐明有反复元素，删除整个区间 leetcode解题代码
/** * 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* deleteDuplicates(ListNode* head) { auto dummy = new ListNode(-1); dummy->next = head; auto p = dummy; while (p->next){ auto q = p->next; while (q && q->val == p->next->val) q = q->next; if (q == p->next->next) p = p->next; else p->next = q; } return dummy->next; }};
合并两个有序链表
leetcode.21
- 链接https://leetcode.cn/problems/...
- 解题办法：归并排序
保护一个以后节点指针
如果list1的值小于list2，指针指向list1并更新以后节点指针和list1的指针
如果list2的值小于list1，指针指向list2并更新以后节点指针和list2的指针
如果两个链表长度不同，当一个链表遍历实现，另一个链表没有遍历实现，以后节点指针指向没有遍历实现的链表 leetcode解题代码
/** * 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* mergeTwoLists(ListNode* list1, ListNode* list2) { auto dummy = new ListNode(-1); auto cur = dummy; while (list1 && list2){ if (list1->val < list2->val){ cur = cur->next = list1; list1 = list1->next; } else{ cur = cur->next = list2; list2 = list2->next; } } if (list1) cur->next = list1; if (list2) cur->next = list2; return dummy->next; }};
leetcode.23
- 链接https://leetcode.cn/problems/...
- 解题办法：归并排序与上一题相似
如何从k个链表中找到最小的值呢？保护一个堆
在c++中保护一个堆用priority_queue，默认是大根堆，所以还须要重载一下比拟函数 leetcode解题代码
/** * 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: struct Cmp{ bool operator() (ListNode* a, ListNode* b){ return a->val > b->val; } }; ListNode* mergeKLists(vector<ListNode*>& lists) { priority_queue<ListNode*, vector<ListNode*>, Cmp> heap; auto dummy = new ListNode(-1); auto cur = dummy; for (auto c: lists) if (c) heap.push(c); while (heap.size()){ auto t = heap.top(); heap.pop(); cur = cur->next = t; if (t->next) heap.push(t->next); } return dummy->next; }};解题参考：https://www.acwing.com/