内容简介:输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。链表结构:这道面试题,太常见了!!!
文章目录
- 面试题25:合并两个 排序 的链表
面试题25:合并两个排序的链表
一、题目描述
输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
链表结构:
public class ListNode { int val; ListNode next=null; ListNode(int val){ this.val=val; } }
二、问题分析
这道面试题,太常见了!!!
不难,但是容易出错。一方面是合并过程链表中间断裂或者没有做到递增,另一方面是代码的鲁棒性不行,也就是忽略了特殊测试(比如任意一个或者两个链表的头结点为null)
最容易想到的思路是再新建一个链表,然后对给出的两个链表分情况讨论即可。
因为合并过程中,每次都是从两个链表中找出较小的一个来链接,因此另一个思路是采用递归来实现:当任意一个链表为null时,直接链接另一个链表即可;其余情况只需要在两个链表中找出较小的一个结点进行链接,该结点的next值继续通过递归函数来链接。
三、问题解答
(1)非递归
public ListNode merge(ListNode list1,ListNode list2) { if(list1==null) return list2; if(list2==null) return list1; ListNode dummyHead=new ListNode(0); //不能为null ListNode p=dummyHead; while(list1!=null && list2!=null){ if(list1.val<list2.val){ p.next=list1; list1=list1.next; }else{ p.next=list2; list2=list2.next; } p=p.next; } p.next = (list1==null?list2:list1); return dummyHead.next; }
(2)递归
public ListNode merge(ListNode list1,ListNode list2) { if(list1==null) return list2; if(list2==null) return list1; if(list1.val<list2.val) { list1.next=merge(list1.next, list2); return list1; }else { list2.next=merge(list1, list2.next); return list2; } }
以上所述就是小编给大家介绍的《剑指Offer对答如流系列 - 合并两个排序的链表》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 剑指Offer对答如流系列 - 顺时针打印矩阵
- 剑指Offer对答如流系列 - 树的子结构
- 剑指Offer对答如流系列 - 对称的二叉树
- 分组字符合并SQL语句 按某字段合并字符串之一(简单合并)
- git 的合并原理(递归三路合并算法)
- git 合并策略
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。