《剑指offer》合并两个排序的链表-ag真人游戏

题目描述

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

解题思路

先判断输入的链表是否为空的指针。如果第一个链表为空，则直接返回第二个链表；如果第二个链表为空，则直接返回第一个链表。如果两个链表都是空链表，合并的结果是得到一个空链表。

两个链表都是排序好的，我们只需要从头遍历链表，判断当前指针，哪个链表中的值小，即赋给合并链表指针即可。使用递归就可以轻松实现。

代码实现(c )

/*
struct listnode {
    int val;
    struct listnode *next;
    listnode(int x) :
            val(x), next(null) {
    }
};*/
class solution {
public:
    listnode* merge(listnode* phead1, listnode* phead2)
    {
        //判断指针是否为空
        if(phead1 == null){
            return phead2;
        }
        else if(phead2 == null){
            return phead1;
        }
        listnode* pmergedhead = null;
        if(phead1->val < phead2->val){
            pmergedhead = phead1;
               pmergedhead->next = merge(phead1->next, phead2);
        }
        else{
            pmergedhead = phead2;
               pmergedhead->next = merge(phead1, phead2->next);
        }
        return pmergedhead;
    }
};

代码实现(python2.7)

# -*- coding:utf-8 -*-
# class listnode:
#     def __init__(self, x):
#         self.val = x
#         self.next = none
class solution:
    # 返回合并后列表
    def merge(self, phead1, phead2):
        # write code here
        if not phead1:
            return phead2
        if not phead2:
            return phead1
        pmergehead = none
        if phead1.val < phead2.val:
            pmergehead = phead1
            pmergehead.next = self.merge(phead1.next, phead2)
        else:
            pmergehead = phead2
            pmergehead.next = self.merge(phead1, phead2.next)
        return pmergehead