[数据结构与算法]leetcode 21.Merge Two Sorted Lists（merge两个排好序的链表）

两个链表已经是升序，现要把它们结合成一个升序排列的链表。

思路：
merge sort
为了方便定义head节点，不至于中间频繁改动位置，始终用head.next指向下一节点。
还要保持一个节点指向最初的head，这样最后直接返回head.next即可。

剩下的就是merge sort，两个节点分别指向list1, list2, 谁的值小，head.next就指向谁，然后节点指针往后移一位。

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        
        ListNode node1 = list1;
        ListNode node2 = list2;
        ListNode head = new ListNode();
        ListNode tmp = head;
        
        while(node1 != null && node2 != null) {
            if(node1.val <= node2.val) {
                tmp.next = node1;
                node1 = node1.next;
            } else {
                tmp.next = node2;
                node2 = node2.next;
            }
            tmp = tmp.next;
        }
        if(node1 != null) tmp.next = node1;
        if(node2 != null) tmp.next = node2;
        return head.next;
    }