[数据结构与算法]剑指offer系列——剑指 Offer 25. 合并两个排序的链表

??前面的话??

大家好！本篇文章将介绍关于数据结构之链表的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]$
$?100<=Node.val<=100$
$l1$ 和 $l2$ 均按 非递减顺序 排列

💡解题思路

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

1. 构造头结点$head$。
2. 两链表同时遍历，将较小值的链表先尾插至$head$结点后（如果相等，随便一个结点尾插即可），结果返回head结点的后一个结点即可。
3. 如果遍历过程中，有链表遍历完或者指针（引用）指向$null$，结束遍历，直接将未遍历完的链表的剩余所有结点尾插至$head$链表后面。

方法2：递归。
步骤：
假设有两个排好序的链表（升序）分别为$list1,list2$，遍历时的引用（指针）分别为$cur1,cur2$。

1. 新建一个链表结点引用（指针）$cur$，递归函数为$mergeTwoLists(structListNode?list1,structListNode?list2)$，返回值为链表引用（指针）。
2. 递归过程中，每次使$cur$指向较小结点$min(cur1，cur2)$，函数返回$cur$。
3. 如果cur1结点数据域的值较小，则$cur$的$next$域指向$mergeTwoLists(cur1.next，cur2)$，反之指向$mergeTwoLists(cur1，cur2.next)$。
4. 递归条件为传入的结点是否为$null$，如果为$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;
}

🌱总结

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