如何找到链表的倒数第k个元素

发布网友发布时间：2022-04-23 09:16

我来回答

共3个回答

懂视网时间：2022-04-23 13:37

本文主要和大家介绍PHP获取链表中倒数第K个节点的方法,涉及php针对链表的遍历、判断等相关操作技巧,需要的朋友可以参考下，希望能帮助到大家。

问题

输入一个链表，输出该链表中倒数第k个结点。

解决思路

注意这个题目是返回节点，而不是返回值。返回值的话可以用栈来存储。返回节点则不能这样做。

设置两个指针，先让第一个指针移动k-1次。然后两个指针同时移动，当第一个指针到达最后一个节点，第二个指针就在倒数第k个节点。

注意边界：K长度可能超出链表长度，所以当第一个指针的next为空时，返回null

实现代码

<?php
/*class ListNode{
 var $val;
 var $next = NULL;
 function __construct($x){
 $this->val = $x;
 }
}*/
function FindKthToTail($head, $k)
{
 if($head == NULL || $k ==0)
 return NULL;
 $pre = $head;
 $last = $head;
 for($i=1; $i<$k; $i++){
 if($last->next == NULL)
 return NULL;
 else
 $last = $last->next;
 }
 while($last->next != NULL){
 $pre = $pre->next;
 $last = $last->next;
 }
 return $pre;
}

相关推荐：

DOM简介及节点、属性、查找节点

PHP实现找出链表中环的入口节点实例详解

jQuery遍历节点方法小结

热心网友时间：2022-04-23 10:45

设置一个队列，长度为K，遍历链表入队，满了就队首的出去。最后队首就是了。

热心网友时间：2022-04-23 12:03

intGetElem();intInstInsert();typedefintElemType;typedefstruct{ElemType*elem;//存储空间基地址intlength;//当前长度intlistsize;//当前分配的存储容量}SqList;intInitList(SqList*L){L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L->elem)exit(-1);//存储空间分配失败L->length=0;//空表长度为0L->listsize=LIST_INIT_SIZE;//初始存储容量printf("线性链表创建成功\n");returnOK;}intInput(SqList*L){ElemTypetemp,*newbase;printf("输入顺序列表的数据，以0为结束标志\n");scanf("%d",&temp);while(temp!=0){if(L->length>=L->listsize){newbase=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!newbase)exit(-1);//存储空间分配失败L->elem=newbase;//空间新基地址L->listsize+=LISTINCREMENT;//增加存储容量}L->elem[L->length++]=temp;scanf("%d",&temp);}printf("输入数据结束！！\n");returnOK;}intOnput(SqList*L){inti=0;printf("输出线性表数据：");while(ilength){printf("%d\t",L->elem[i]);i++;}printf("\n");}intClearList(SqList*L){L->length=0;printf("清除成功!\n");returnOK;}voidListEmpty(SqListL){if(L.elem!=NULL)printf("true!\n");elseprintf("false!\n");}voidListLength(SqListL){printf("线性表的长度是：%d\n",L.length);return;}intGetElem(SqListL,inti,SqList*e){e=L.elem[i-1];returne;}voidPriorElem(SqListL,intcur_e,SqList*pre_e){if(cur_e!=L.elem[0]){pre_e=L.elem[0];printf("前驱值为：%d\n",pre_e);}elseprintf("pre_e无意义\n");}voidNextElem(SqListL,intcur_e,SqList*next_e){if(cur_e!=L.elem[L.length-1]){next_e=L.elem[L.length-1];printf("后继值为：%d\n",next_e);}elseprintf("next_e无意义\n");}intListInsert(SqList*L,inti,inte){ElemType*newbase,*p,*q;if(1>i||i>(L->length+1))return-1;if(L->length>=L->listsize){//新增内存newbase=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//开辟新内存空间if(!newbase)exit(-1);//存储分配失败L->elem=newbase;//新基地址L->listsize+=LISTINCREMENT;//新增内存容量}q=&(L->elem[i-1]);for(p=&(L->elem[L->length-1]);p>=q;p--){*(p+1)=*p;}*q=e;++L->length;returnOK;}intListDelete(SqList*L,inti,inte){ElemType*p,*q;if(iL->length)return-1;q=&(L->elem[i-1]);e=L->elem[i-1];p=L->elem+L->length-1;for(;p>=q;q++)*q=*(q+1);--L->length;printf("删除的值为：%d\n",e);returnOK;}