剑指offer题目16：合并两个排序的链表

/**
* 题目16：合并两个排序的链表
* 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
*/

//解法1：新建一个链表用于存储合并后的链表(或者使用ArrayList存储合并后的链表)
//时间、空间复杂度O(m+n)、O(1)   27ms
public ListNode Merge_16(ListNode list1,ListNode list2) {
    ListNode root=new ListNode(0);
    ListNode tmp=root;
    while (list1!=null && list2!=null){
        if(list1.val>=list2.val){
            tmp.next=list2;
            list2=list2.next;
        }
        else{
            tmp.next=list1;
            list1=list1.next;
        }
        tmp=tmp.next;
    }
    if(list1!=null) tmp.next=list1;
    else if(list2!=null) tmp.next=list2;
    return root.next;
}
//解法2：使用递归，先取出最小值，然后接下来的两条链表进行递归
//时间、空间复杂度O(m+n)、O(1)     24ms
public ListNode Merge_16_2(ListNode list1,ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    if(list1.val>list2.val) return Merge_16_2(list2,list1);
    list1.next=Merge_16_2(list1.next, list2);
    return list1;
}
//解法3：不开辟空间，在原链表上操作     30ms
public ListNode Merge_16_3(ListNode list1,ListNode list2) {
    if (list1 == null) return list2;
    if (list2 == null) return list1;
    if(list1.val>list2.val) return Merge_16_3(list2,list1);
    ListNode root=list1,tmp;//list1的第一个节点最小
    while (list1.next!=null && list2!=null){
        if(list2.val>=list1.next.val) list1=list1.next;
        else {
            tmp = list1.next;//记录list1的下一个节点tmp(比当前list2节点node大)
            list1.next = list2;//将list2节点插入在list之后
            list2 = list2.next;//list2往后移一位，成为新的list2链表
            list1 = list1.next;//list1往后移一位，指向node节点
            list1.next = tmp;//将node节点的next指针重新指向tmp
        }
    }
    if(list2 !=null) list1.next=list2;
    return root;
}