实现链表合并

/**
 * 实现两个链表的融合；
 * 2,4,8，
 *,3,6,9,
 * 结果 2,3,4,6,8,9
 */
public static ListNode MergeTwoLists(ListNode head1, ListNode head2) {

    if (head1 == null || head2 == null) {
        return head1 == null ? head2 : head1;
    }


    //保存是哪个head,便于最后返回；
    ListNode head = head1.value > head2.value ? head2 : head1;

    ListNode pre = head;
    ListNode cur1 = pre.next;
    ListNode cur2 = pre == head1 ? head2 : head1;

    //pre选择去连接cur1 cur2中小的那个；
    while (cur1 != null && cur2 != null) {
        if (cur1.value < cur2.value) {
            pre.next = cur1;
            pre = cur1;
            cur1 = cur1.next;
        } else {
            pre.next = cur2;
            pre = cur2;
            cur2 = cur2.next;
        }
    }
    pre.next = cur1 == null ? cur2 : cur1;
    return head;
}