[剑指offer][Java]合并两个排序的链表

题目

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

程序核心思想

这个题目的思想还是很清晰的。
首先找一条头结点比较小的，让它作为合并后的链表的头结点。然后依次检查这条链表的后面的节点，直到一个节点的后面的节点比另一条链表的头结点大，然后把这个节点的next指针指向另一个链表的头结点。然后依次检查这条节点的后面的节点，直到一个节点的数大于上一个节点（改变next指针的节点）的后面一个节点（因为改变指针的节点已经是合并链表的一部分了，它已经排好序了），然后依次重复这些动作，直到有一个链表全部进入合并链表。

Tips

• 我设了两个指针来指向用于比较的两条链表的节点，有一个比较重要的点是，这两个指针每经过链表的合并之后，就需要互换指向。这是因为在我的程序中，始终是min1指向min2的，由于是小的指向大的，所以min1始终要指向比较小的那个节点，即合并链表的尾端。

代码

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 != null && list2 == null)    return list1;
        if(list1 == null && list2 != null)    return list2;
        if(list1 == null && list2 == null)    return null;
        
        ListNode min1 = list1;
        ListNode min2 = list2;
        ListNode temp = list1;
        ListNode answer = list1;
        
        if(list1.val > list2.val){
            min1 = list2;
            min2 = list1;
            answer = list2;
        }
        
        
        while(min1 != null && min2 != null){
            while(min1.next != null && min1.next.val <= min2.val){
                min1 = min1.next;
            }
            temp = min1;
            min1 = min1.next;
            temp.next = min2;
            temp = min2;
            min2 = min1;
            min1 = temp;
        }

        return answer;
    }
}