合并两个排序的链表 -- java

输入两个单调递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。例如下图中的链表1和链表2，则合并之后的升序链表如链表3所示。

链表的节点定义如下：

public class ListNode {
    int value;
    ListNode next = null;

    public ListNode() {
    }

    public ListNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "value=" + value +
                '}';
    }
}

首先分析合并两个链表的过程。我们的分析从合并两个链表的头结点开始。链表1的头结点的值小于链表2的头结点的值，因此链表1的头结点将是合并后链表的头结点，如图所示：

我们继续合并两个链表中剩余的结点。在两个链表中剩下的结点依然是排序的，因此合并这两个链表的步骤和前面的步骤是一样的。我们还是比较两个头结点的值。此时链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点的值将是合并剩余结点得到的链表的头结点。我们把这个结点和前面合并链表时得到的链表的尾节点链接起来，如图所示。

当我们得到两个链表中较小的头节点并把它链接到已经合并的链表之后，两个链表剩余的节点依然是排序的，因此合并的步骤和之前的步骤是一样的。

这就是典型的递归过程，我们可以定义递归函数完成这一合并过程。

public class Merge {
    public static ListNode merge(ListNode head1, ListNode head2) {
        // 解决鲁棒性的问题
        if (head1 == null) {
            return head2;
        } else if (head2 == null){
            return head1;
        }

        ListNode mergedHead = null;

        if (head1.value < head2.value) {
            mergedHead = head1;
            mergedHead.next = merge(head1.next, head2);
        } else {
            mergedHead = head2;
            mergedHead.next = merge(head1, head2.next);
        }

        return mergedHead;
    }

    // 测试
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node3 = new ListNode(3);
        ListNode node5 = new ListNode(5);
        ListNode node7 = new ListNode(7);
        node1.next = node3;
        node3.next = node5;
        node5.next = node7;


        ListNode node2 = new ListNode(2);
        ListNode node4 = new ListNode(4);
        ListNode node6 = new ListNode(6);
        ListNode node8 = new ListNode(8);

        node2.next = node4;
        node4.next = node6;
        node6.next = node8;

        ListNode mergedNode = merge(node1, node2);
        print_listNode(mergedNode);
    }

    // 打印listNode(用作测试)
    public static void print_listNode(ListNode listNode) {
        while (listNode != null) {
            System.out.print(listNode.value+" ");
            listNode = listNode.next;
        }
        System.out.println();
    }
}

来自：

《剑指Offer》
Coding-Interviews/合并两个排序的链表.md at master · todorex/Coding-Interviews