当前位置： 首页 > article >正文

可视化图解算法：链表中倒数（最后）k个结点

article 2025/3/20 2:51:46

1. 题目

描述

输入一个长度为 n 的链表，设链表中的元素的值为ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

数据范围：0≤n≤105，0 ≤ai≤109，0 ≤k≤109

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

例如输入{1,2,3,4,5},2时，对应的链表结构如下图所示：

其中蓝色部分为该链表的最后2个结点，所以返回倒数第2个结点（也即结点值为4的结点）即可，系统会打印后面所有的节点来比较。

示例1

输入：

{1,2,3,4,5},2

返回值：

{4,5}

说明：

返回倒数第2个节点4，系统会打印后面所有的节点来比较。

示例2

输入：

{2},8

返回值：

{}

2. 解题思路

获取链表的倒数第K个节点，最先想到的是先获取链表的长度n（共多少个节点，时间复杂度为n），之后再从前向后查找，遍历n-k个节点。

此题还有一种巧妙的解法：双指针法。通过此方法可以遍历一次查找到对应的节点。

假如链表结构如下图所示，给定k=2，即查找倒数第2个节点（值为4的节点）：

这时，可以通过以下步骤完成：

第一步：定义快慢指针。

第二步：移动快指针 k 次（每次移动1个节点）。

k=2，即快指针先移动k次（每次一个节点），这时fast会指向3节点。

第三步：快慢指针一起移动（每次移动1个节点），一直到快指针fast指向Null停下来。

第四步：快指针指向为None，慢指针指向的节点为：倒数第k个节点。

如果文字描述的不太清楚，你可以参考视频的详细讲解。

  • Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1370264

  • Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1366720

  • Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364397

3. 编码实现

3.1 Python编码实现

class ListNode:
    def __init__(self, x):
        self.val = x  # 链表的数值域
        self.next = None  # 链表的指针域


# 从链表节点尾部添加节点
def insert_node(node, value):
    if node is None:
        print("node is None")
        return
    # 创建一个新节点
    new_node = ListNode(value)
    cur = node
    # 找到链表的末尾节点
    while cur.next is not None:
        cur = cur.next
    # 末尾节点的next指针域连接新节点
    cur.next = new_node


# 打印链表（从链表头结点开始打印链表的值）
def print_node(node):
    cur = node
    # 遍历每一个节点
    while cur is not None:
        print(cur.val, end="\t")
        cur = cur.next  # 更改指针变量的指向
    print()


#
#
# @param pHead ListNode类
# @param k int整型
# @return ListNode类
#
class Solution:
    def FindKthToTail(self, pHead: ListNode, k: int) -> ListNode:
        # write code here
        # 1.  定义快慢指针
        fast = pHead
        slow = pHead

        # 2. 移动快指针  k 次（每次移动1个节点）
        for i in range(k):
            if fast is None:
                return None  # k大于链表长度的情况
            fast = fast.next

        # 3. 快慢指针一起移动（每次移动1个节点）
        while fast is not None:
            fast = fast.next
            slow = slow.next

        # 4. 快指针指向为None，慢指针指向的节点为：到时候第k个节点
        return slow


if __name__ == '__main__':
    head = ListNode(1)
    insert_node(head, 2)
    insert_node(head, 3)
    insert_node(head, 4)
    insert_node(head, 5)
    print_node(head)

    s = Solution()
    node = s.FindKthToTail(head, 2)
    print(node.val)
    print_node(node)

3.2 Java编码实现

package LL08;


public class Main {
    //定义链表节点
    static class ListNode {
        private int val;  //链表的数值域
        private ListNode next; //链表的指针域

        public ListNode(int data) {
            this.val = data;
            this.next = null;
        }
    }

    //添加链表节点
    private static void insertNode(ListNode node, int data) {
        if (node == null) {
            return;
        }
        //创建一个新节点
        ListNode newNode = new ListNode(data);
        ListNode cur = node;
        //找到链表的末尾节点
        while (cur.next != null) {
            cur = cur.next;
        }
        //末尾节点的next指针域连接新节点
        cur.next = newNode;
    }

    //打印链表（从头节点开始打印链表的每一个节点）
    private static void printNode(ListNode node) {
        ListNode cur = node;
        //遍历每一个节点
        while (cur != null) {
            System.out.print(cur.val + "\t");
            cur = cur.next; //更改指针变量的指向
        }
        System.out.println();
    }


    public static class Solution {
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         * @param pHead ListNode类
         * @param k     int整型
         * @return ListNode类
         */
        public ListNode FindKthToTail(ListNode pHead, int k) {
            // write code here
            // 1. 定义快慢指针
            ListNode fast = pHead;
            ListNode slow = pHead;

            // 2. 移动快指针 k 次（每次移动1个节点）
            for (int i = 0; i < k; i++) {
                if (fast == null) {
                    return null; //k大于链表长度的情况
                }
                fast = fast.next;
            }

            // 3. 快慢指针一起移动（每次移动1个节点）
            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }

            // 4. 快指针指向为null，慢指针指向的节点为：到时候第k个节点
            return slow;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        insertNode(head, 2);
        insertNode(head, 3);
        insertNode(head, 4);
        insertNode(head, 5);
        printNode(head);

        Solution solution = new Solution();
        ListNode node = solution.FindKthToTail(head, 2);
        System.out.println(node.val);
        printNode(node);
    }
}

3.3 Golang编码实现

package main

import "fmt"

// ListNode 定义链表节点
type ListNode struct {
	Val  int       //链表的数值域
	Next *ListNode //链表的指针域
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead ListNode类
 * @param k int整型
 * @return ListNode类
 */
func FindKthToTail(pHead *ListNode, k int) *ListNode {
	// write code here
	// 1. 定义快慢指针
	fast := pHead
	slow := pHead

	// 2. 移动快指针 k 次（每次移动1个节点）
	for i := 0; i < k; i++ {
		if fast == nil {
			return nil //k大于链表长度的情况
		}
		fast = fast.Next
	}

	// 3. 快慢指针一起移动（每次移动1个节点）
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	// 4. 快指针指向为nil，慢指针指向的节点为：到时候第k个节点
	return slow
}
func main() {
	head := ListNode{Val: 1}
	head.Insert(2)
	head.Insert(3)
	head.Insert(4)
	head.Insert(5)
	head.Print()

	node := FindKthToTail(&head, 2)
	fmt.Println(node.Val)
	node.Print()
}

// Insert 从链表节点尾部添加节点
func (ln *ListNode) Insert(val int) {
	if ln == nil {
		return
	}
	//创建一个新节点
	newNode := &ListNode{Val: val}
	cur := ln
	//找到链表的末尾节点
	for cur.Next != nil {
		cur = cur.Next
	}
	//末尾节点的next指针域连接新节点
	cur.Next = newNode
}

// Print 从链表头结点开始打印链表的值
func (ln *ListNode) Print() {
	if ln == nil {
		return
	}
	cur := ln
	//遍历每一个节点
	for cur != nil {
		fmt.Print(cur.Val, "\t")
		cur = cur.Next //更改指针变量的指向
	}
	fmt.Println()
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解。

  • Python版本：哔哩哔哩_bilibili

  • Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili

  • Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364397

4.小结

获取链表的倒数（最后）第k个节点，可以通过快慢指针快速获取到：

  • 定义快慢指针。

  • 移动快指针 k 次（每次移动1个节点）。

  • 快慢指针一起移动（每次移动1个节点），一直到快指针fast指向Null停下来。

  • 快指针指向为None，慢指针指向的节点为：倒数第k个节点。

更多算法视频讲解，你可以从以下地址找到：

  • Python编码实现：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1509965

  • Java编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1510007

  • Golang编码实现：数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1509945

对于链表的相关操作，我们总结了一套【可视化+图解】方法，依据此方法来解决链表相关问题，链表操作变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：问渠那得清如许？为有源头活水来。


http://www.kler.cn/a/591991.html

相关文章：

  • 使用py-ffmpeg批量合成视频的脚本
  • CentOS7 安装 jdk8（Java安装）
  • Next.js 的渲染体系架构
  • Spring Boot 核心知识点深度详解：自动化配置 (Auto-configuration) - 解锁 Spring Boot 的 “魔法”
  • 【从零开始学习计算机科学】软件工程（三）需求工程
  • 《算法笔记》9.2小节——数据结构专题(2)-＞二叉树的遍历 问题 B: 二叉树
  • 批量清空 Excel 文档主题、标记、作者、保存时间、总编辑时间元数据
  • 23年蓝桥杯 ———— 阶乘求和
  • rk3588 linux的rootfs.img挂载后通过chroot切换根目录安装应用提示空间不足
  • 一、Redis简介篇
  • 一文梳理清楚Vsync/Choreographer/SurfaceFlinger/Surface/SurfaceHolder/硬件刷新频率关系
  • Springboot是怎么保证WebSocket的链接对象是唯一的
  • 孜然SEO静态页面生成系统V1.0
  • 卷积神经网络 - 卷积层
  • 《基于Spring Boot+Vue的智慧养老系统的设计与实现》开题报告
  • 【鸿蒙】封装日志工具类 ohos.hilog打印日志
  • pthon转换SR785频谱仪的代码
  • 基于mediapipe深度学习的运动人体姿态提取系统python源码
  • 项目开发 1-确定选题，制作原型
  • 【css酷炫效果】纯CSS实现波浪形分割线