合并两个有序单链表

一、问题描述

给定两个单链表，都是递增有序的，将它们合并，使合并后的链表仍然有序。

二、解题思路

这种链表的问题我们最先想到是递归算法了，将两个链表的第一个元素进行比较 ，取较小的那个做为新链表的头，剩下的分别作为两个链表的头结点，当其中一个链表全都比较完了，则直接返回另一个链表。

三、代码实现

public class ListNode {
    int value;  
    ListNode next;

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

   /**
     * 合并两个有序单链表
     * @param firstHead 第一个链表
     * @param secondHead 第二个链表
     * @return
     */
    public ListNode mergeTwoListNode(ListNode firstHead, ListNode secondHead) {
        // 递归出口
        if (firstHead == null)  {
            return secondHead;
        }
        if (secondHead == null) {
            return firstHead;
        }

        ListNode mergeNode;  // 合并后的新链表

        if (firstHead.value < secondHead.value) {
            mergeNode = firstHead;
            // 取下次合并的最小的节点，递归
            mergeNode.next = mergeTwoListNode(firstHead.next, secondHead);
        } else {
            mergeNode = secondHead;
            mergeNode.next = mergeTwoListNode(firstHead, secondHead.next);
        }
        return mergeNode;

    }