[LeetCode OJ]- Merge Two Sorted Lists

题目要求:合并两个单向已排序的链表l1和l2,返回新的链表。

思路:该问题跟合并两个已排序的数组很像,合并两个已排序的数组是使用三个指针,从尾向头扫描,不断加入到数组中。而单向链表不能从尾往头加,这时候考虑也用两个“指针”从头往尾扫,加入到第三个新的链表中。

起始状态:比较l1的头结点和l2的头结点的大小,让较小的(假如为l1)作为新的链表的头节点,然后再递归地比较l1.next和l2的“头节点”(l1.next可以看做一个新的链表,它去除了刚刚加入新链表的数)直到两个链表中有一个为空链表为止。

还需要考虑特殊情况,当l1为空或者l2为空时,剩下的另一个链表的数据可以直接追加到新链表中,不需要再比较。

最终返回新链表的头节点即可。

代码如下。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 转载请注明出处://www.greatytc.com/p/c65d9d753c31 在上一篇博客《数据结构...
    Alent阅读 3,528评论 4 74
  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,322评论 0 25
  • 1 序 2016年6月25日夜,帝都,天下着大雨,拖着行李箱和同学在校门口照了最后一张合照,搬离寝室打车去了提前租...
    RichardJieChen阅读 5,148评论 0 12
  • //leetcode中还有花样链表题,这里几个例子,冰山一角 求单链表中结点的个数----时间复杂度O(n)这是最...
    暗黑破坏球嘿哈阅读 1,533评论 0 6
  • 下学后来往的人上上下下,路灯影子盖住了那位传单老人。 1和室友经过,谈到最近没有发传单的人,连补课也无门可走,恰逢...
    sang鱼阅读 257评论 0 1