Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

思路分析：这题是 LeetCode Sort List需要使用的merge两个有序链表使得结果仍然有序这个子过程，详细图解可以参见 LeetCode Sort List。时间复杂度O（m+n），空间复杂度O（1），是常量。与这题关系密切的题目还有Merge Sorted Array，Merge k Sorted Lists，Merge Intervals等，可以比较一下解法，熟练掌握。

AC Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode fakeHead = new ListNode(0);
        fakeHead.next = head1;
        ListNode pre = fakeHead;
        while(head1 != null && head2 != null){
            if(head1.val < head2.val){
                head1 = head1.next;
            } else {
                ListNode next = head2.next;
                head2.next = pre.next;
                pre.next = head2;
                head2 = next;
            }
            pre = pre.next;
        }
        if(head2 != null){
            pre.next = head2;
        }
        return fakeHead.next;
    }
}

LeetCode Merge Two Sorted Lists