首页 前端 TypeScript 正文

获取链表中倒数第K个节点

前言

给定一个单向链表的头节点,如何获取该链表中倒数第K个节点(从1开始计数)?本文将带着大家一起解决这个问题,欢迎各位感兴趣的开发者阅读本文。

思路分析

我们通过一个例子来做进一步的分析:

  • 准备一个链表,它有6个节点,从头节点开始,其值依次为:1、3、5、9、15、21

  • 获取该链表的倒数第3个节点

遍历两次链表

根据单向链表的定义,我们可知:想要获取它的某个节点,只能从头节点开始顺着其指针往后查找。假设整个链表有n个节点,那么倒数第K个节点就是从头节点开始的第n-K+1个节点。如果我们能够得到节点数n,那么只需要从头节点开始往后走n-k+1步就可以了。想要得到节点数n,就需要定义一个变量,从头开始遍历链表,每经过一个节点,这个变量就自增1。

也就是说,我们需要遍历链表两次,第一次计算出链表中节点的个数,第二次就能获取倒数第K个节点,如下图所示:

  • 第1次遍历链表拿到了链表的长度n=6

  • 第2次遍历链表获取到了倒数第3个节点处(6-3+1)的值9

获取链表中倒数第K个节点  第1张

遍历一次链表

遍历两次链表来解决这个问题并不是最优解,我们换个思路来考虑下这个问题:准备两个指针。

  • 第一个指针从链表的头部开始遍历向前走k-1(3-1=2)步,第二个指针保持不动

  • 从第k步开始,第二个指针也开始从链表的头指针开始遍历,两指针同时向前走。

  • 由于两个指针的距离始终保持在k-1,当第一个指针到达链表的尾节点时,第二个指针正好指向倒数第k个节点

获取链表中倒数第K个节点  第2张

实现代码

通过上面的分析,我们知道了如何用双指针的思路,只遍历一次链表就能获取链表的倒数第K个节点。接下来,我们来看下代码实现。

首先,我们设计一个名为GetLinkedListNode的类:

  • 内部有2个私有变量

    • pNext P1指针

    • pHead P2指针

  • 构造方法接受1个参数:链表头节点

    • 对参数进行校验

    • 修改两个指针的指向:默认指向链表头节点

export class GetLinkedListNode {
  // p1指针
  private pNext: ListNode;
  // p2指针(与p1指针的距离始终保持在k-1)
  private pHead: ListNode;

  constructor(listHead: ListNode) {
    if (listHead == null) {
      throw new Error("链表头节点不能为空");
    }

    // 初始化两个指针指向
    this.pNext = listHead;
    this.pHead = listHead;
}

上述代码中,我们用了一个自定义类型ListNode,它描述了一个链表的节点应该包含哪些属性,对此感兴趣的开发者请移步我的另一篇文章:链表与变相链表的实现

紧接着,实现获取倒数第K个节点函数:

  • 接受一个参数K(从1开始),对参数进行有效性校验

  • 修改p1指针的指向,将其指向k-1节点,k的范围也要做一下规避处理(其值大于链表总节点数)

  • 同步修改p1、p2指针的指向,直至p1指针指向尾节点,p2指针正好指向倒数第K个节点

  // 获取倒数第K个节点
  getCountdownNode(k: number): ListNode {
    if (k <= 0) {
      throw new Error("需要获取的倒数节点数必须大于0");
    }

    // p1指针先走,将其指向链表的k-1位置
    for (let i = 0; i < k - 1; i++) {
      // k可能出现大于链表总节点的情况,需要进行规避
      if (this.pNext.next != null) {
        this.pNext = this.pNext.next;
      } else {
        throw new Error("需要找的节点不存在");
      }
    }

    // 两个指针同时向前走,直至p1指针指向尾节点
    while (this.pNext.next) {
      this.pNext = this.pNext.next;
      if (this.pHead.next) {
        this.pHead = this.pHead.next;
      }
    }

    // p2节点正好指向倒数第K个节点
    return this.pHead;
  }

完整代码请移步?:GetLinkedListNode.ts

小tips:我们在写代码的时候,一定要尽可能地考虑各种边界情况的处理,最大程度的避免一些错误的发生,提升代码的健壮性。

例如上述代码中所做的处理,最大程度的避免了程序因取不到值而引发的异常报错问题,我们也管这种做法称为防御性编程

这是一种良好的编程习惯,在编写代码的时候多问问自己“如果不······那么······”这样的问题,提前预见在什么地方可能会出现问题,并为这些可能出现的问题制定处理方式。这样,当异常情况发生时,软件的行为也尽在我们的掌握之中,而不至于出现不可预见的事情。

测试用例

接下来,我们将前言中的例子代入上个章节所实现的函数中,验证下它能否得出正确的结果。

const linkedList = new LinkedList();
linkedList.push(1);
linkedList.push(3);
linkedList.push(5);
linkedList.push(9);
linkedList.push(15);
linkedList.push(21);

const getLinkedListNode = new GetLinkedListNode(linkedList.getHead());
const resultNode = getLinkedListNode.getCountdownNode(3);
console.log(resultNode);

运行结果如下所示,成功的解决了文章前言中所讲的问题。

获取链表中倒数第K个节点  第3张

完整代码请移步?:GetLinkedListNode-test.ts

注意:上述代码中用到的LinkedList是自定义的一个类,它实现了链表这个数据结构,对其原理感兴趣的开发者请移步我的另一篇文章?:链表与变相链表的实现

示例代码

本文所列举的代码,其完整版请移步?:

写在最后

至此,文章就分享完毕了。

我是神奇的程序员,一位前端开发工程师。

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注?

  • 本文首发于神奇的程序员公众号,未经许可禁止转载?

原文;https://juejin.cn/post/7103911740856860702
打赏
海报

本文转载自互联网,旨在分享有价值的内容,文章如有侵权请联系删除,部分文章如未署名作者来源请联系我们及时备注,感谢您的支持。

转载请注明本文地址:https://www.shouxicto.com/article/5984.html

相关推荐

详解TypeScript中的泛型

详解TypeScript中的泛型

   前言    给定一个单向链表的头节点,如何获取该链表中倒数第K个节点(从1开始计数)?本文将带着大家一起解决这个问题,...

TypeScript 2022.08.20 0 1086

获取链表中倒数第K个节点

获取链表中倒数第K个节点

   前言    给定一个单向链表的头节点,如何获取该链表中倒数第K个节点(从1开始计数)?本文将带着大家一起解决这个问题,...

TypeScript 2022.06.01 0 1022

TypeScript 泛型从新手到入门

TypeScript 泛型从新手到入门

   前言    给定一个单向链表的头节点,如何获取该链表中倒数第K个节点(从1开始计数)?本文将带着大家一起解决这个问题,...

TypeScript 2022.05.31 0 1027

发布评论

ainiaobaibaibaibaobaobeishangbishibizuichiguachijingchongjingdahaqiandaliandangaodw_dogedw_erhadw_miaodw_tuzidw_xiongmaodw_zhutouganbeigeiliguiguolaiguzhanghahahahashoushihaixiuhanheixianhenghorse2huaixiaohuatonghuaxinhufenjiayoujiyankeaikeliankouzhaokukuloukunkuxiaolandelinileimuliwulxhainiolxhlikelxhqiuguanzhulxhtouxiaolxhwahahalxhzanningwennonuokpinganqianqiaoqinqinquantouruoshayanshengbingshiwangshuaishuijiaosikaostar0star2star3taikaixintanshoutianpingtouxiaotuwabiweifengweiquweiwuweixiaowenhaowoshouwuxiangjixianhuaxiaoerbuyuxiaokuxiaoxinxinxinxinsuixixixuyeyinxianyinyueyouhenghengyuebingyueliangyunzanzhajizhongguozanzhoumazhuakuangzuohenghengzuoyi
支付宝
微信
赞助本站