如何找到链表倒数第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个结点。当遍历到链表的最后一个结点时，指针p所指向的结点即为所查找的结点。

（2）详细步骤：

详细实现步骤:增加两个指针变量和一个整型变量，从链表头向后遍历，其中指针p1指向当前遍历的结点，指针p指向p1所指向结点的前k个结点

如果p1之前没有k个结点，那么p指向表头结点。用整型变量i表示当前遍历了多少个结点，

当i>k时，指针p随着每次遍历，也向前移动一个结点。

当遍历完成时，p或者指向表头结点，或者指向链表中倒数第k个位置上的结点。

（3）代码实现：

#include<stdio.h> #include<stdlib.h> typedef struct Node { int data; struct Node *next; }Node,*LinkList; LinkList CreateList(int n) { LinkList h,r,s; h=(LinkList)malloc(sizeof(Node)); r=h; int i; int x; for(i=0;i<n;i++) { s=(LinkList)malloc(sizeof(Node)); scanf("%d",&x); s->data=x; r->next=s; r=s; } r->next=NULL; h=h->next; return h; } void PrintList(LinkList L) { while(L) { printf("%d\t",L->data); L=L->next; } printf("\n"); } LinkList FindElement(LinkList list,int k) { LinkList p,p1; p=list; p1=list->next; int i=1; while(p1) { p1=p1->next; i++; if(i>k) p=p->next; } if(p==list) return 0; else { printf("%d\n",p->data); } } int main() { LinkList L1; int n,k; printf("请输入L1链表的长度，以回车结束，然后输入结点的值："); scanf("%d",&n); L1=CreateList(n); printf("L1链表为："); PrintList(L1); printf("请输入k的值："); scanf("%d",&k); printf("倒数第%d个结点为：",k); FindElement(L1,k); printf("\n"); return 0; }