【算法刷题之链表篇（2）】

1.leetcode-23. 合并 K 个升序链表（较难）

（1）题目描述

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

（2）方法一：顺序合并

思路：
首先写出合并两个链表的代码：
1.定义两个指针分别位于两个链表的头处，再定义一个哨兵位用于接受元素；
2.两个链表头处的指针开始遍历，并且相互比较，此时哨兵位newnode的节点head指向比较中更小的那个元素。
3.将此链表往前移一位，并且哨兵位的head也往前移动以为。
重复上述步骤即可合并两个链表；
对于k组链表的合并：
对于所给k组链表，从头开始遍历，逐步将两个链表先合并为一个，然后再与后面合并，这样就可以调用上述的两两合并的函数
代码实现

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

（3）方法二：分治合并

考虑优化方法一，用分治的方法进行合并。
将 k 个链表配对并将同一对中的链表合并；
第一轮合并以后， k 个链表被合并成了k/2个链表，然后是k/4
重复这一过程，直到我们得到了最终的有序链表。

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* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l];
        if (l > r) return nullptr;
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }
};

（4）方法三：使用优先队列合并

思路
这个方法和前两种方法的思路有所不同，我们需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。
代码实现

class Solution {
public:
    struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val;
        }
    };
    priority_queue <Status> q;
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        for (auto node: lists) {
            if (node) q.push({node->val, node});
        }
        ListNode head, *tail = &head;
        while (!q.empty()) {
            auto f = q.top(); q.pop();
            tail->next = f.ptr; 
            tail = tail->next;
            if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
        }
        return head.next;
    }
};

代码解释：
这段代码是一个用于合并K个有序链表的解决方案。它使用了优先队列（priority_queue）来选择当前K个链表中最小的节点，并将其连接到结果链表中。
在mergeKLists函数中，定义了一个结构体Status，用于存储节点的值和指针。结构体中还重载了小于运算符，以便在优先队列中按照节点值的大小进行排序。
首先，将K个链表中的第一个节点加入到优先队列中。然后，创建一个虚拟头节点head和一个指针tail指向它。接下来，进入循环，直到优先队列为空。在每次循环中，取出优先队列中的最小节点f，将其连接到结果链表的末尾，即tail->next = f.ptr，然后更新tail指针为新的末尾节点。如果最小节点f的指针f.ptr还有下一个节点，将下一个节点的值和指针加入到优先队列中。重复这个过程，直到所有链表中的节点都被处理完。
最后，返回结果链表的头节点，即head.next。

2.leetcode-92. 反转链表 II

（1）题目描述

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
（注意left和right是位置）

（2）方法及思路（穿针引线）

思路示意图如下

如图所示，我们需要找到left前一个结点，也需要找到right后一个节点，
并在反转链表前将其与前后断开。
具体思路如下：
.第 1 步：先将待反转的区域反转；
第 2 步：把 pre 的 next 指针指向反转以后的链表头节点，把反转以后的链表的尾节点的 next 指针指向 succ。

（3）代码实现

class Solution {
    private:
        void reverseLinkedList(ListNode* head)
        {
            ListNode* pre=NULL;
            ListNode* cur=head;
            while(cur!=NULL)
            {
                ListNode* next=cur->next;
                cur->next=pre;
                pre=cur;
                cur=next;
            }
        }
   public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        ListNode* newnode=new ListNode(0);
        ListNode* prev=newnode;
        prev->next=head;
       for (int i = 0; i < left - 1; i++) {
            prev = prev->next;
        }
        ListNode* leftnode=prev->next;
        ListNode* rightnode=prev;
        while(right-left+1>0)
        {
            rightnode=rightnode->next;
            right--;
        }
        ListNode* curr=rightnode->next;
        prev->next=NULL;
        rightnode->next=NULL;
        reverseLinkedList(leftnode);
        prev->next=rightnode;
        leftnode->next=curr;
        return newnode->next;
    }
};

3.leetcode-2. 两数相加

（1）题目描述

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

（2）方法及思路（模拟）

思路：由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry，则它们的和为 n1+n2+carry，其中，答案链表处相应位置的数字为(n1+n2+carry)%10，而新的进位值为(n1+n2+carry)/10。

（3）代码实现

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *head = nullptr, *tail = nullptr;
        int carry = 0;
        while (l1 || l2) {
            int n1 = l1 ? l1->val: 0;
            int n2 = l2 ? l2->val: 0;
            int sum = n1 + n2 + carry;
            if (!head) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;
            if (l1) {
                l1 = l1->next;
            }
            if (l2) {
                l2 = l2->next;
            }
        }
        if (carry > 0) {
            tail->next = new ListNode(carry);
        }
        return head;
    }
};

4.leetcode-21. 合并两个有序链表

（1）题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

（2）方法一：迭代

思路：
我们可以用迭代的方法来实现上述算法。当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。
算法
首先，我们设定一个哨兵节点 prehead ，这可以在最后让我们比较容易地返回合并后的链表。我们维护一个 prev 指针，我们需要做的是调整它的 next 指针。然后，我们重复以下过程，直到 l1 或者 l2 指向了 null ：如果 l1 当前节点的值小于等于 l2 ，我们就把 l1 当前的节点接在 prev 节点的后面同时将 l1 指针往后移一位。否则，我们对 l2 做同样的操作。不管我们将哪一个元素接在了后面，我们都需要把 prev 向后移一位。
在循环终止的时候， l1 和 l2 至多有一个是非空的。由于输入的两个链表都是有序的，所以不管哪个链表是非空的，它包含的所有元素都比前面已经合并链表中的所有元素都要大。这意味着我们只需要简单地将非空链表接在合并链表的后面，并返回合并链表即可。
代码实现

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }
        prev.next = l1 == null ? l2 : l1;
        return prehead.next;
    }
}

（3）方法二：递归

思路
我们可以如下递归地定义两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

1.如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。
2.否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。
3.如果两个链表有一个为空，递归结束。
代码如下：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==NULL)
        {
            return list2;
        }
        else if(list2==NULL)
        {
            return list1;
        }
        else if(list1->val<list2->val)
        {
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }
        else
        {
            list2->next=mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

5.leetcode-24. 两两交换链表中的节点

（1）题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

（2）方法一：迭代

思路：
1.首先创建一个哨兵位newnode，并定义一个指针prev指向它。
2.在prev后定义一个当前节点n1，后一个为n2，并先将prev指向n2，n2，指向n1，再把n1指向原来n2的下一位
3.最后更新prev节点到n1的新位置。

代码实现

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* newnode=new ListNode(0);
        ListNode* prev=newnode;
        prev->next=head;
        while(prev->next&&prev->next->next)
        {
            ListNode* n1=prev->next;
            ListNode* n2=prev->next->next;
            prev->next=n2;
            n1->next=n2->next;
            n2->next=n1;
            prev=n1;
        }
        return newnode->next;
    }
};

（3）方法二：递归

思路与算法
可以通过递归的方式实现两两交换链表中的节点。
递归的终止条件是链表中没有节点，或者链表中只有一个节点，此时无法进行交换。
1.如果链表中至少有两个节点，则在两两交换链表中的节点之后，原始链表的头节点变成新的链表的第二个节点，原始链表的第二个节点变成新的链表的头节点。
2.链表中的其余节点的两两交换可以递归地实现。在对链表中的其余节点递归地两两交换之后，更新节点之间的指针关系，即可完成整个链表的两两交换。

代码实现：文章来源地址https://www.toymoban.com/news/detail-671949.html

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

到了这里，关于【算法刷题之链表篇（2）】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！