剑指 offer 笔记 16 | 合并两个排序的链表

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

思路分析

题目描述可知，合并两个链表是从两个链表的头节点开始。而链表 1 的头节点小于 链表 2 的头节点的值，所以链表 1 的头节点合并链表后的头节点。

然后接着比较 2 节点而 3 节点，因为哪个链表的值小就合并都已经合并的链表去，所以后续的合并步骤是重复的，可以用递归。

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){ // 判断是否为空链表
            return list2;
        }else if(list2 == null){
            return list1;
        }
        
        ListNode MergeList = null; //设置合并后的链表
        
        if(list1.val < list2.val){ //如果 链表 1 的值 < 链表 2 的值

            MergeList = list1; //链表 1 的第一个值，赋值到 合并链表
            MergeList.next = Merge(list1.next, list2); //下一轮合并，链表 1 从第二个开始

        }else{//如果 链表 1 的值 > 链表 2 的值
            MergeList = list2; //链表 1 的第一个值，赋值到 合并链表
            MergeList.next = Merge(list1, list2.next); //下一轮合并，链表 2 从第二个开始
        }
        return MergeList; 
    }
}

参考文献：《剑指offer》， 写于 2019年6月19日21:41:30