数据结构之线性表——LeetCode:82. 删除排序链表中的重复元素 II,21. 合并两个有序链表，23. 合并 K 个升序链表

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;
    }
};

代码思路

1. mergeTwoLists 函数

   • 这个函数用于合并两个升序链表 a 和 b。
   • 首先处理特殊情况，如果其中一个链表为空，直接返回另一个链表。
   • 创建一个虚拟头节点 head 和一个指向虚拟头节点的指针 tail。同时，定义指针 aPtr 和 bPtr 分别指向两个输入链表的头节点。
   • 进入一个循环，只要 aPtr 和 bPtr 都不为空，就继续循环。在循环中，比较 aPtr 和 bPtr 所指节点的值，将较小值的节点连接到 tail->next，并相应地移动较小值节点的指针和 tail 指针。
   • 循环结束后，将剩余的非空链表连接到 tail->next。
   • 最后，返回虚拟头节点 head 的下一个节点，即为合并后的链表的头节点。

2. mergeKLists 函数

   • 这个函数用于合并 k 个升序链表。
   • 定义指针 ans 初始化为 nullptr，用于存储合并后的链表。
   • 遍历输入的链表数组 lists，每次将当前的合并结果 ans 和数组中的一个链表进行合并，更新 ans 为新的合并结果。
   • 最终，返回 ans，即合并后的链表的头节点。