剑指Offer 25. 合并两个排序的链表

Description

难度简单：剑指 Offer 25. 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：
0 <= 链表长度 <= 1000

Solution

以 l1 为合并后的链表的开头，依次取 l2 中的一连串处于 l1 中两节点之间的值，合并到 l1 中。以下图为例：

在 l2 中找到处于 l1 中 1 -> 3 之间的子链表

将 l2 中 2->3 链接到 l1 中

重复上述步骤，直到两个链表排序成功

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val > l2.val){    // 如果 l2 的 head 结点大于 l1 的 head 结点，交换位置 l1 和 l2
            ListNode temp = l1;
            l1 = l2;
            l2 = temp;
        }
        // 将 l2 中 start2 到 end2 指向的链表合并到 l1 中 start1 到 start1.next 之间
        ListNode start1 = l1;
        while(start1.next != null && l2 != null){  // 结束条件
            if (start1.next.val < l2.val){  // 跳过 l1 中比 l2 开头小的元素 
                start1 = start1.next;
                continue;
            }   
            ListNode start2 = l2, end2 = l2;  // 选取 start2 到 end2 之间的链表
            while(end2.next != null && end2.next.val <= start1.next.val)
                end2 = end2.next;
            // 更新 l2 的指向
            l2 = end2.next;
            // 将 l2 中 start2 到 end2 链接到 l1 中 start1 到 start1.next 之间
            end2.next = start1.next;
            start1.next = start2;
            // 更新 l1 中 start1 的指向
            start1  = end2.next;
        }
        // 判断 l2 中是否还存有元素
        if (l2 != null)
            start1.next = l2;
        return l1;
    }
}

Solution2

用归并排序的思路，解决两个链表合并的问题

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                tail.next = l1;
                l1 = l1.next;
            }else{
                tail.next = l2;
                l2 = l2.next;
            }
            tail = tail.next;
        }
        if(l1 != null)
            tail.next = l1;
        if(l2 != null)
            tail.next = l2;
        return dummyHead.next;
    }
}