题目----力扣--合并两个有序链表

Skrrapper

发布于 2024-06-18 14:54:48

1160

发布于 2024-06-18 14:54:48

文章被收录于专栏：技术分享技术分享

题目

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

解法

这里我们使用迭代的方式将两个有序链表合并成一个有序链表。首先判断两个输入的链表是否为空，如果有一个为空则直接返回另一个链表。然后定义两个指针l1和l2分别指向两个链表的头部，再定义一个新的链表头指针newHead和尾指针newTail。

在循环中，比较l1和l2当前节点的值，将较小的节点插入到新链表中，并更新newTail指针。循环直到其中一个链表遍历完毕。最后判断剩余的链表，将剩余的节点直接连接到新链表的尾部。

最后返回新链表的头部即可。这种方法的时间复杂度为O(m+n)，其中m和n分别为两个链表的长度。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    // 判断list1或者list2是否为空表，如果是则直接返回另一个表即可（基于原先的表已经为有序，所以无需重新排序）
    if (list1 == NULL) {
        return list2;
    }
    if (list2 == NULL) {
        return list1;
    }

    ListNode *l1, *l2;
    l1 = list1, l2 = list2;
    ListNode *newHead, *newTail;
    newHead = newTail = NULL;

    while (l1 && l2) {
        // 判断两个链表中相应元素的大小
        if (l1->val < l2->val) {
            // 插入l1（先插入较小的）
            // 在此之前要判断链表是否为空

            if (newHead == NULL) {
                // 链表为空 头尾指针都指向该节点
                newHead = newTail = l1;
            } else {
                // 链表不为空
                newTail->next = l1;
                newTail = newTail->next;
            }

            l1 = l1->next;
        } else {
            // 插入l2
            if (newHead == NULL) {
                // 链表为空 头尾指针都指向该节点
                newHead = newTail = l2;
            } else {
                // 链表不为空
                newTail->next = l2;
                newTail = newTail->next;
            }

            l2 = l2->next;
        }
    }
    // 跳出循环存在两种情况：
    // A.l1空 l2不为空
    if (l1) {
        newTail->next = l1;
        // newTail =newTail->next(指向的是新一串的头结点)
    }
    // B.l2空 l1不为空
    if (l2) {
        newTail->next = l2;
        // newTail = newTail->next;
    }
    return newHead;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-18，如有侵权请联系 cloudcommunity@tencent.com 删除

指针