前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >《剑指offer》第11期:两个链表题目

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

作者头像
ConardLi
发布2019-05-23 21:49:32
3050
发布2019-05-23 21:49:32
举报
文章被收录于专栏:code秘密花园

链表中倒数第k个节点

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

思路

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

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

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

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

代码

代码语言:javascript
复制
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的情况,取对方节点返回。

代码

代码语言:javascript
复制
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;
    }
本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-02-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 code秘密花园 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 链表中倒数第k个节点
  • 思路
  • 代码
  • 合并两个有序链表
  • 思路
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档