面试题25：合并两个排序的链表

题目：输入两个递增排序的链表，合并这两个链表并时新链表中的节点仍然是递增排序的。
思路：这是一个递归的过程。构建两个指针P1和P2分别指向两个链表的头部，比较P1和P2的值，把较小值作为头节点，依次重复如上操作。
解决方案：

public class Question25 {
    static class ListNode{
        int value;
        ListNode next;
        public ListNode(int value){
            this.value = value;
        }
    }

    public static ListNode merge(ListNode head1, ListNode head2){
        if (head1 == null){
            return head2;
        }else if (head2 == null){
            return head1;
        }

        ListNode mergeHead = null;
        if (head1.value < head2.value){
            mergeHead = head1;
            mergeHead.next = merge(head1.next, head2);
        }
        if (head1.value > head2.value){
            mergeHead = head2;
            mergeHead.next = merge(head1, head2.next);
        }
        return mergeHead;
    }

    public static void main(String[] args) {
        ListNode pHead1 = new ListNode(1);
        ListNode pAhead1 = new ListNode(3);
        ListNode pBhead1 = new ListNode(5);
        ListNode pChead1 = new ListNode(7);
        pHead1.next = pAhead1;
        pAhead1.next = pBhead1;
        pBhead1.next = pChead1;

        ListNode pHead2 = new ListNode(2);
        ListNode pAhead2 = new ListNode(4);
        ListNode pBhead2 = new ListNode(6);
        ListNode pChead2 = new ListNode(8);
        pHead2.next = pAhead2;
        pAhead2.next = pBhead2;
        pBhead2.next = pChead2;
        System.out.println(merge(pHead1, pHead2).value);
    }
}