剑指Offer（十六）：合并两个排序的链表

2017年12月3日15:22:41 16 8,051 °C

摘要

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

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

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

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

2、代码

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;
    }
};

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

# -*- 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

微信公众号

分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。

版权声明：本站原创文章，于2017年12月3日15:22:41，由 Jack Cui 发表，共 324 字。
转载请注明：剑指Offer（十六）：合并两个排序的链表 | Jack Cui

发表评论取消回复

目前评论：16 其中：访客 10 博主 6

政治部 上海市卢湾区电信 1
回复 2019年5月14日下午6:50 沙发
这个递归如何才能跳出来？
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年5月14日下午9:34 1层
  @政治部条件在最前面，没有子节点了就返回。
政治部 中国移动 1
回复 2019年5月15日下午10:32 板凳
那这个函数最终返回的是递归终止条件里面的返回值吗？return pHead2或者 return pHead1？
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年5月16日下午6:35 1层
  @政治部递归到最里面，然后再从里往外释放，最终到的就是需要的链表。
小小毛 天津市天津大学 3
回复 2019年6月27日下午12:24 地板
关于Python的算法，严格意义上不算递归吧。没有“有回”呀，这算是迭代吧。
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年6月27日下午9:42 1层
  @小小毛递归一定有return，要不然程序就死了。
yyx 北京市电信 2
回复 2019年8月23日上午10:00 4楼
楼主你好～问个有点傻的问题。。是每次调用这个递归函数他才有一个return是吗？所以就是返回pMergeHead然后加上如果两个链表长度不相等剩下的部分，是吗
- Jack Cui Admin 北京市百度网讯科技联通节点
  回复 2019年8月26日上午9:49 1层
  @yyx 不是啊，不满足条件，不会return的，return了就不往下递归了，开始往上返回。
zymize 黑龙江省哈尔滨市电信 1
回复 2020年4月24日上午8:44 5楼
请问您如果只用python编写代码，不会C++编写代码，今年8月份左右找工作，从现在开始牛客网剑指offer，到8月份能找工作吗？本专业是电子信息工程
- Jack Cui Admin 北京市通州区联通
  回复 2020年4月24日上午9:58 1层
  @zymize 看岗位的，开发岗必须c++，算法岗看面试官心情，c++和python都行。刷题时间是够的，但还得补其他专业知识，时间紧，加油～
  - zymize 黑龙江省哈尔滨市电信 1
    回复 2020年4月24日上午10:05 2层
    @Jack Cui 非常感谢。请问如果是算法岗的话大概还需要掌握哪些专业知识呢？麻烦能给些建议吗？我是女生，逻辑上面没有那么强。或者有没有推荐女生去的岗？
    - Jack Cui Admin 北京市百度网讯科技联通节点
      回复 2020年4月24日上午11:06 3层
      @zymize 那时间有点紧迫的，看我这篇：
      https://cuijiahua.com/blog/2018/04/life_2.html
      你应该能有个大概的了解，去各个公司招聘网站看一看吧，看下喜欢哪个，看看要求，合不合适自己看了更清楚。
      不过不论哪个岗位，时间都是有些紧张的，得抓紧了。
- 一书一世界 黑龙江省哈尔滨市双城区联通 2
  回复 2020年7月20日下午7:30 1层
  @zymize 同学你现在找到了吗？咱俩同专业，可能还是同一个学校？？？
小白广东省广州市联通 1
回复 2021年2月22日上午8:59 6楼
python3.*的解法，可行不？
a = [1,2,3,4,5]
b = [2,3,4,5,6]
a.extend(b)
a.sort()
print(a)
IDFC 云南省昆明市呈贡县电信 1
回复 2021年9月17日下午11:04 7楼
返回的是链表的尾节点吧。
IDFC 云南省昆明市电信 1
回复 2021年9月18日上午8:47 8楼
如果两个链表不一样长返回的是比另一条链表所有数都大的数所在的节点