描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

示例1

输入：
{1,3,5},{2,4,6}

返回值：
{1,2,3,4,5,6}

思路

这道题和《合并两个有序数组》道理一样，先设置一个哑节点，哑节点的next指针指向结果的头节点。然后遍历两个链表，值小的那个加入到结果链表后，直到两个链表都遍历完。

AC 代码

public ListNode Merge(ListNode list1,ListNode list2) {
           if (list1 == null) {
               return list2;
           } else if (list2 == null) {
               return list1;
           }
        // 定义哑节点
        ListNode dum = new ListNode(0);
        // 记录一下头节点
        ListNode result = dum;
        // 当连个链表都没有遍历完时
        while(list1 != null && list2 != null) {
            // 值小的一方先放入结果链表中
            if (list1.val > list2.val) {
                dum.next = list2;
                list2 = list2.next;
            } else {
                dum.next = list1;
                list1 = list1.next;
            }
            dum = dum.next;
        }
        // 将剩余没有遍历放入结果链表中
        dum.next = list1 == null ? list2 : list1;
        // 返回头节点
        return result.next;
    }

时间复杂度：O(m+n), m 为list1的长度，n 为list2的长度。
空间复杂度：O(m + n)。

最后

大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。