算法题-合并两个排序的链表

[编程题]合并两个排序的链表

时间限制：1秒 空间限制：32768K

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

1.递归解法

• 思路

  1、本题很显然用递归方式很好实现，同时需要注意下算法的鲁棒性即——首先处理空链表，当其中一个为空链表时，直接输出另一个；当两个均为空链表时，输出null
  2、比较 list1 和 list2 的头结点，较小的头结点作为合并后新链表的头结点
  3、确定新链表的头结点之后，就可以递归比较余下的结点了

递归版本C++
C++

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/
class Solution {
public:
ListNode* Merge(ListNode* pHeadFirst, ListNode* pHeadSec)
    {
        ListNode* pMerge=NULL;
        if(pHeadFirst==NULL){
           return pHeadSec;
        }
        if(pHeadSec==NULL){
            return pHeadFirst;
        }
    //以上处理空链表
        if(pHeadFirst->val > pHeadSec->val){//分别比较两个链表头结点的大小,较小的头结点作为合并后新链表的头结点
            pMerge=pHeadSec;
            pMerge->next=Merge(pHeadFirst,pHeadSec->next);
        }else{
            pMerge=pHeadFirst;
            pMerge->next=Merge(pHeadFirst->next,pHeadSec);
        }
        return pMerge;
    }
};

python递归版本

# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
    def Merge(self,pHeadFirst,pHeadSec):
        if pHeadFirst is None:
            return pHeadSec
        if pHeadSec is None:
            return pHeadFirst
        pMerge=ListNode(None)
        if pHeadFirst.val<pHeadSec.val:
            pMerge=pHeadFirst
            pMerge.next=self.Merge(pHeadFirst.next,pHeadSec)
        else:
            pMerge=pHeadSec
            pMerge.next=self.Merge(pHeadFirst,pHeadSec.next)
        return pMerge        

---

2.非递归解法

当然本题还有非递归的版本实现，思想与递归大致一致。每次比较链表1和链表2结点的值，选择较小的结点作为下一个链接的结点。
- 思路：

比较两个链表的首结点，哪个小的的结点则合并到新链表尾结点，并向前移动一个结点。
步骤一结果会有一个链表先遍历结束，或者没有,新链表尾结点指向剩余未遍历结束的链表,
返回新链表首结点

C++非递归版本实现

class Solution {
public:
    ListNode* Merge(ListNode* pHeadFirst, ListNode* pHeadSec){
        ListNode* pMerge = NULL;
        ListNode* cur = NULL;

        if(pHeadFirst == NULL)
            return pHeadSec;
        if(pHeadSec == NULL)
            return pHeadFirst;

        while(pHeadFirst != NULL && pHeadSec != NULL){
            if(pHeadFirst->val <= pHeadSec->val){
                if(pMerge == NULL){
                    cur = pMerge = pHeadFirst;
                } else {
                    cur->next = pHeadFirst;
                    cur = cur->next;
                }
                pHeadFirst = pHeadFirst->next;
            } else {
                if(pMerge == NULL){
                    cur = pMerge = pHeadSec;
                } else {
                    cur->next = pHeadSec;
                    cur = cur->next;
                }
                pHeadSec = pHeadSec->next;
            }
        }         
        if(pHeadFirst == NULL){
            cur->next = pHeadSec;
        }
        if(pHeadSec == NULL){
            cur->next = pHeadFirst;
        }
        return pMerge;
    }
};

Python非递归版本实现

# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHeadFirst, pHeadSec):
        # write code here
        cur = ListNode(0)
        pMerge = cur     
        while pHeadFirst and pHeadSec:
            if pHeadFirst.val >= pHeadSec.val:
                cur.next = pHeadSec
                pHeadSec = pHeadSec.next
            else:
                cur.next = pHeadFirst
                pHeadFirst = pHeadFirst.next

            cur = cur.next
        if pHeadFirst:
            cur.next = pHeadFirst
        elif pHeadSec:
            cur.next = pHeadSec
        return pMerge.next