合并两个有序链表

这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战

leetcode 合并两个有序链表

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

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
复制代码

示例 2：

输入：l1 = [], l2 = []
输出：[]
复制代码

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]
复制代码

解题：要合并两个链表可以使用迭代的方法来实现，循环遍历l1和l2两个链表，l1并且l2都不是空时，分别取出l1，l2头节点的值来判断哪个链表的小，然后将其添加到合并链表后面。首先创建一个空的合并链表，使用一个指针初始指向合并链表，每次移动指针来添加节点，当l1并且l2不是空时就继续比较两个链表（因为l1、l2是从小到大有序的链表，当一个链表为空时，另外一个链表就可以直接添加到合并链表后面了）如果l1节点值小于l2节点值，那么就把l1节点添加到合并链表后面，并且l1链表后移一位，否则l2小也重复这个操作，然后合并链表的指针也得指向下一个节点，循环这个操作，直到l1或者l2有一个链表是空就结束，最后直接在结果链表后面拼接剩余非空的链表就可以了。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode mergeNode = new ListNode();
        ListNode pointerNode = mergeNode;
        // l1,l2 不为空时循环遍历
        while (l1 != null && l2 != null) {
            // 判断两个链表 较小的添加到合并链表后面，并且小链表后移
            if (l1.val < l2.val) {
                pointerNode.next = l1;
                l1 = l1.next;
            } else {
                pointerNode.next = l2;
                l2 = l2.next;
            }
            // 指针后移
            pointerNode = pointerNode.next;
        }
        // l1、l2不空的链表 添加到合并链表后面
        if (l1 != null) {
            pointerNode.next = l1;
        }
        if (l2 != null) {
            pointerNode.next = l2;
        }
        return mergeNode.next;
    }
}
复制代码

或者递归，将两个链表中头结点较小的与剩下的节点合并。首先如果l1或者l2为空了就不需要合并直接返回，否则判断l1和l2中头结点小的链表，合并剩余的链表去递归。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 有一个为空 直接返回另一个
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        // 比较获取小链表
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
复制代码