82. 删除排序链表中的重复元素 II
题目描述
82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
运行代码
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (!head) {return head;}ListNode* dummy = new ListNode(0, head);ListNode* cur = dummy;while (cur->next && cur->next->next) {if (cur->next->val == cur->next->next->val) {int x = cur->next->val;while (cur->next && cur->next->val == x) {cur->next = cur->next->next;}}else {cur = cur->next;}}return dummy->next;}
};代码思路
- 首先，处理输入链表为空的情况，如果
head为nullptr，直接返回head。 - 创建一个虚拟头节点
dummy，并将其next指针指向输入链表的头节点head。这样做是为了方便处理头节点可能被删除的情况。 - 定义指针
cur并初始化为dummy，用于遍历链表并判断是否有重复节点。 - 进入一个循环，只要
cur->next和cur->next->next不为nullptr，就继续循环。这个条件确保在检查是否有重复节点时，有足够的节点可供比较。 - 如果发现当前节点
cur->next的值等于下一个节点cur->next->next的值，说明存在重复节点：- 记录当前重复节点的值为
x。 - 进入一个循环，只要
cur->next不为nullptr且其值等于x，就将cur->next指针指向下一个节点的下一个节点，即跳过所有值为x的重复节点。
- 记录当前重复节点的值为
- 如果没有发现重复节点，即当前节点
cur->next的值不等于下一个节点cur->next->next的值，说明当前节点不重复，将cur指针向后移动一位，即cur = cur->next。 - 循环结束后，返回虚拟头节点
dummy的下一个节点，即为删除重复节点后的链表的头节点。
21. 合并两个有序链表
题目描述
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
运行代码
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dum = new ListNode(0);ListNode* cur = dum;while (list1 != nullptr && list2 != nullptr) {if (list1->val < list2->val) {cur->next = list1;list1 = list1->next;}else {cur->next = list2;list2 = list2->next;}cur = cur->next;}cur->next = list1 != nullptr ? list1 : list2;return dum->next;}
};代码思路
一、整体方法概述
这段代码的目的是合并两个升序链表为一个新的升序链表。它通过比较两个链表当前节点的值，将较小值的节点依次连接到新链表中，直到其中一个链表遍历完，然后将剩余的链表连接到新链表的末尾。
二、函数分析
- 首先，创建一个虚拟头节点
dum，并将指针cur初始化为指向dum。虚拟头节点的作用是方便返回合并后的链表，避免处理头节点为空的特殊情况。 - 进入一个循环，只要
list1和list2都不为nullptr，就继续循环。这个循环的目的是逐个比较两个链表的节点值，并将较小值的节点连接到新链表中。 - 在循环中，如果
list1当前节点的值小于list2当前节点的值，那么将cur的next指针指向list1，然后将list1指针向后移动一位，即list1 = list1->next。如果list1当前节点的值大于等于list2当前节点的值，那么将cur的next指针指向list2，然后将list2指针向后移动一位，即list2 = list2->next。无论哪种情况，都将cur指针向后移动一位，即cur = cur->next。 - 循环结束后，说明其中一个链表已经遍历完。此时，判断
list1是否为nullptr，如果不是，则将cur的next指针指向list1；如果是，则将cur的next指针指向list2。这样就将剩余的链表连接到了新链表的末尾。 - 最后，返回虚拟头节点
dum的下一个节点，即为合并后的链表的头节点。
三、算法思路总结
该算法利用了两个链表已经有序的特点，通过比较节点值的方式逐步构建新的合并链表。时间复杂度取决于两个链表的总长度，为O（m+n) ，其中 m和n 分别是两个链表的长度。空间复杂度为O(1) ，因为只使用了有限的额外指针变量，不随输入规模增长。
23. 合并 K 个升序链表
题目描述
23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
运行代码
/*** 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 *a, ListNode *b) {if ((!a) || (!b)) return a ? a : b;ListNode head, *tail = &head, *aPtr = a, *bPtr = b;while (aPtr && bPtr) {if (aPtr->val < bPtr->val) {tail->next = aPtr; aPtr = aPtr->next;} else {tail->next = bPtr; bPtr = bPtr->next;}tail = tail->next;}tail->next = (aPtr ? aPtr : bPtr);return head.next;}ListNode* mergeKLists(vector<ListNode*>& lists) {ListNode *ans = nullptr;for (size_t i = 0; i < lists.size(); ++i) {ans = mergeTwoLists(ans, lists[i]);}return ans;}
};代码思路
-
mergeTwoLists函数- 这个函数用于合并两个升序链表
a和b。 - 首先处理特殊情况，如果其中一个链表为空，直接返回另一个链表。
- 创建一个虚拟头节点
head和一个指向虚拟头节点的指针tail。同时，定义指针aPtr和bPtr分别指向两个输入链表的头节点。 - 进入一个循环，只要
aPtr和bPtr都不为空，就继续循环。在循环中，比较aPtr和bPtr所指节点的值，将较小值的节点连接到tail->next，并相应地移动较小值节点的指针和tail指针。 - 循环结束后，将剩余的非空链表连接到
tail->next。 - 最后，返回虚拟头节点
head的下一个节点，即为合并后的链表的头节点。
- 这个函数用于合并两个升序链表
-
mergeKLists函数- 这个函数用于合并
k个升序链表。 - 定义指针
ans初始化为nullptr，用于存储合并后的链表。 - 遍历输入的链表数组
lists，每次将当前的合并结果ans和数组中的一个链表进行合并，更新ans为新的合并结果。 - 最终，返回
ans，即合并后的链表的头节点。
- 这个函数用于合并
