合并两个排序链表

先分析一下合并过程。假设链表1的头结点的值小于链表2的头结点的值，则链表1的头结点作为合并后的链表的头结点。然后继续合并两个链表中剩余的结点。两个链表中剩下的结点依然是排序的，所以合并这两个链表的步骤和前面的步骤一样。这是典型的递归过程，可以定义递归函数来完成这一合并过程。

这里写图片描述

  private ListNode merge(ListNode pHead1,ListNode pHead2){
        if (pHead1==null){
            return pHead2;
        }
        if (pHead2==null){
            return pHead1;
        }
        ListNode pMergedHead=null;
        if (pHead1.getValue()<pHead2.getValue()){
            pMergedHead=pHead1;
            pMergedHead.setNext(merge(pHead1.getNext(),pHead2));
        }else {
            pMergedHead=pHead2;
            pMergedHead.setNext(merge(pHead1,pHead2.getNext()));
        }
        return pMergedHead;
    }

原文链接http://write.blog.csdn.net/mdeditor#!postId=53207040