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

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

题目

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

示例 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
  • l1l2 均按 非递减顺序 排列

解法

这里我们使用迭代的方式将两个有序链表合并成一个有序链表。首先判断两个输入的链表是否为空,如果有一个为空则直接返回另一个链表。然后定义两个指针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;
}
目录
相关文章
|
11小时前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
1天前
|
容器
【LeetCode刷题】栈和队列题目练习~
【LeetCode刷题】栈和队列题目练习~
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(4)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1天前
|
存储 算法
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总(1)
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
【经典LeetCode算法题目专栏分类】【第8期】滑动窗口:最小覆盖子串、字符串排列、找所有字母异位词、 最长无重复子串
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
1天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值