文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2024-12-02 00:13

关注

思路分析

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

遍历两次链表

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

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

遍历一次链表

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

实现代码

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

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

pNext P1指针;

pHead P2指针。

对参数进行校验;

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

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个节点
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);

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

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

注意:上述代码中用到的LinkedList是自定义的一个类,它实现了链表这个数据结构。

示例代码

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

来源:神奇的程序员内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯