⭐️前面的话⭐️

大家好！本篇文章将介绍关于数据结构之链表的OJ题，来自力扣：21. 合并两个有序链表 或 剑指 Offer 25. 合并两个排序的链表 题解，展示代码语言暂时为：Java语言与C语言。（后续会更新C++代码）

?博客主页：未见花闻的博客主页
?欢迎关注?点赞?收藏⭐️留言?
?本文由未见花闻原创，CSDN首发！
?首发时间：?2021年11月30日?
✉️坚持和努力一定能换来诗与远方！
?刷题推荐书籍：?《剑指offer专项版》，?《剑指offer第2版》
?参考在线编程网站：?牛客网?力扣
博主的码云gitee，平常博主写的程序代码都在里面。
博主的github，平常博主写的程序代码都在里面。
?作者水平很有限，如果发现错误，一定要及时告知作者哦！感谢感谢！

⭐️剑指 Offer 25. 合并两个排序的链表⭐️

?题目详情

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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

提示：
两个链表的节点数目范围是

[

0

,

50

]

[0, 50]

[0,50]

−

100

<

=

N

o

d

e

.

v

a

l

<

=

100

-100 <= Node.val <= 100

−100<=Node.val<=100

l

1

l1

l1 和

l

2

l2

l2 均按 非递减顺序 排列

?解题思路

方法1：构造一个头结点，遍历两链表，按数据域值大小按顺序尾插至头结点后。
步骤：

1. 构造头结点$head$
2. 两链表同时遍历，将较小值的链表先尾插至$head$
3. 如果遍历过程中，有链表遍历完或者指针（引用）指向$null$

方法2：递归。
步骤：
假设有两个排好序的链表（升序）分别为

l

i

s

t

1

,

l

i

s

t

2

list1,list2

list1,list2，遍历时的引用（指针）分别为

c

u

r

1

,

c

u

r

2

cur1,cur2

cur1,cur2。

1. 新建一个链表结点引用（指针）$cur$
2. 递归过程中，每次使$cur$
3. 如果cur1结点数据域的值较小，则$cur$
4. 递归条件为传入的结点是否为$null$

?源代码

方法1：Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //1. 新建一个结点用作头结点，然后同时遍历两个链表，将值小的结点按顺序插入在这个头结点后
        ListNode newNode = new ListNode();
        ListNode tmp = newNode;
        //2.同时遍历两个链表，将数据域值小的结点依次插入值newNode结点后面，形成一个新链表，如果遍历出现null，则结束遍历
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tmp.next = l1;
                l1 = l1.next;
                tmp = tmp.next;
            }
            else {
                tmp.next = l2;
                l2 = l2.next;
                tmp = tmp.next;
            }
        }
        //3.对两链表经过遍历相同次数后，将更长链表后面的结点接入到新链表后
        if (l1 != null) {
            tmp.next = l1;
        }
        if (l2 != null) {
            tmp.next = l2;
        }
        //4.我们新建结点newNode后一个结点开始的链表为合并后的链表
        return newNode.next;
    }
}

方法2：C

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if (!l1)
        return l2;
    if (!l2)
        return l1;//一个链表为空则返回另一个链表

    struct ListNode* cur = NULL;

    if (l1->val <= l2->val)
    {
        cur = l1;
        cur->next = mergeTwoLists(l1->next, l2);
    }
    else
    {
        cur = l2;
        cur->next = mergeTwoLists(l1, l2->next);
    }
    return cur;
}

?总结

抓住链表是已经排序好这一点，遍历比较两链表的值，将链表进行重排。

觉得文章写得不错的老铁们，点赞评论关注走一波！谢谢啦！