专栏首页code秘密花园《剑指offer》第11期:两个链表题目

《剑指offer》第11期:两个链表题目

链表中倒数第k个节点

输入一个链表,输出该链表中倒数第k个结点。

思路

简单思路: 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

优化:设定两个节点,间距相差k个节点,当前面的节点到达终点,取后面的节点。

前面的节点到达k后,后面的节点才出发。

本题目着重考察代码鲁棒性、容错率: 需要考虑head为null,k为0,k大于链表长度的情况

代码

function FindKthToTail(head, k) {
      if (!head || !k) return null;
      let front = head;
      let behind = head;
      let index = 1;
      while (front.next) {
        index++;
        front = front.next;
        if (index > k) {
          behind = behind.next;
        }
      }
      return (k <= index) && behind;
    }

合并两个有序链表

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

思路

链表头部节点比较,取较小节点。

小节点的next等于小节点的next和大节点的较小值。

如此递归。

返回小节点。

考虑代码的鲁棒性,也是递归的终止条件,两个head为null的情况,取对方节点返回。

代码

function Merge(pHead1, pHead2) {
      if (!pHead1) {
        return pHead2;
      }
      if (!pHead2) {
        return pHead1;
      }
      let head;
      if (pHead1.val < pHead2.val) {
        head = pHead1;
        head.next = Merge(pHead1.next, pHead2);
      } else {
        head = pHead2;
        head.next = Merge(pHead1, pHead2.next);
      }
      return head;
    }

本文分享自微信公众号 - code秘密花园(code_mmhy),作者:ConardLi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-02-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指offer》11.链表中倒数第k个节点

    简单思路: 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

    ConardLi
  • 【算法专栏】二叉树的下一个节点

    给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

    ConardLi
  • npm install 原理分析

    开门见山,npm install 大概会经过上面的几个流程,本篇文章来讲一讲各个流程的实现细节、发展以及为何要这样实现。

    ConardLi
  • [面试] 聊聊你对 Vue.js 框架的理解

    本文为一次前端技术分享的演讲稿,所以尽力不贴 Vue.js 的源码,因为贴代码在实际分享中,比较枯燥,效果不佳,而更多的是以图片和文字的形式进行表达。

    1024 FED
  • 浅谈链表--数据结构的重要根基

    链表、列表,说起来有点相似,作用也有点类似,但可别傻傻分不清楚。我们一般说的列表,是一个连续的序列,用来存储一组数据。而链表,虽然也是有序的存储结构,但它不限定...

    Crossin先生
  • LeetCode之链表(10)

    今天有点闲,就来连刷几道题,下次不这样干了,有点hold不住,建议以后保持平衡刷题规律!

    公众号guangcity
  • leetcode链表之环路检测

    有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。

    codecraft
  • LeetCode 203:移除链表元素

    Remove all elements from a linked list of integers that have value val.

    爱写bug
  • LeetCode 203:移除链表元素

    Remove all elements from a linked list of integers that have value val.

    爱写bug
  • leetcode链表之环路检测

    有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。

    codecraft

扫码关注云+社区

领取腾讯云代金券