如何找到链表倒数第k个节点的值？

本文共计722个文字，预计阅读时间需要3分钟。

问题描述：已知一个带有表头结点的单链表，结点结构为：+ 假设该链表只给出了头指针list。+ 在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置的结点。

算法设计：

1.初始化两个指针p1和p2，都指向链表的头结点。

2.将p2向前移动k个位置。

3.当p2到达链表末尾时，p1指向倒数第k个结点。

4.如果p2在移动过程中遇到空指针，说明链表长度小于k，返回错误信息。

5.如果p2移动到链表末尾，p1指向倒数第k个结点，返回p1。

代码实现：

pythonclass ListNode: def __init__(self, val=0, next=None): self.val=val self.next=next

def find_kth_to_last(head, k): p1=p2=head for _ in range(k): if p2 is None: return 链表长度小于k p2=p2.next while p2: p1=p1.next p2=p2.next return p1

问题描述

已知一个带有表头结点的单链表，结点结构为：

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1;否则，只返回0。

解决方法

（1）算法的基本思想：

从头至尾遍历单链表，并用指针p指向当前结点的前k个结点。