C++实现LeetCode(21.混合插入有序链表)

C++实现LeetCode(21.混合插入有序链表)

题目描述

给你两个有序链表的头节点 l1 和 l2，请你将它们合并成一个新的有序链表，并返回新链表的头节点。

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

题解

这道题的思路比较简单，我们可以创建一个新链表，根据题目要求，将原链表中的节点依次加入新链表，最后返回新链表的头节点即可。具体的步骤如下：

1. 定义一个哨兵节点 res 作为新链表的头节点(因为链表常常涉及头节点特殊处理，所以定义哨兵节点可以避免复杂的头节点判断)
2. 定义两个指针 p1 和 p2 分别指向原链表 l1 和 l2 的头节点
3. 创建一个指针 cur，指向新链表的最后一个节点
4. 比较 p1 和 p2 对应节点的大小，将值小的节点接入新链表。
5. 若 p1 所指节点值小，则将 p1 所指节点接入新链表，并将指针 p1 后移一位
6. 若 p2 所指节点值小或者二者相等，则将 p2 所指节点接入新链表，并将指针 p2 后移一位
7. 若 p1 或 p2 中至少有一个已经遍历完，此时就将另一个链表剩余的节点全部加入新链表
8. 返回头节点 res.next

对于链表的题目，一定要保证指针的正确性, 同时为了避免链表断裂，可以创建哨兵节点来简化节点插入。

代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *res = new ListNode(-1); // 哨兵节点
        ListNode *cur = res; // 指针cur指向新连接的链表的最后一个节点

        ListNode *p1 = l1, *p2 = l2;
        // 采用while循环实现遍历
        while(p1 != nullptr && p2 != nullptr) {
            if(p1 -> val < p2 -> val) {
                cur -> next = p1;
                p1 = p1 -> next; // p1往后走一步
            } else {
                cur -> next = p2;
                p2 = p2 -> next; // p2往后走一步        
            }
            cur = cur -> next;
        }

        // 将剩余的节点连接到新链表中
        if(p1 != nullptr) cur -> next = p1;
        if(p2 != nullptr) cur -> next = p2;

        return res -> next;
    }
};

示例

例如，输入两个链表 l1 = [1,2,4], l2 = [1,3,4]，则调用 mergeTwoLists(l1, l2) 后得到的链表是 [1,1,2,3,4,4]。

此外，当其中一个链表为空时，返回的新链表也为空，例如，输入两个链表 l1 = [], l2 = [1,2,3]，则调用 mergeTwoLists(l1, l2) 后得到的链表是[1,2,3]。