找出链表倒数第n个节点元素的二个方法
2023-06-13 09:15:12 时间
方法一：利用两个指针p,q，首先将q往链表尾部移动n位，然后再将p、q一起往后移，那么当q达到链表尾部时，p即指向链表的倒数第n个节点。
复制代码代码如下:
node*find_nth_to_last(node*head,intn){if(head==NULL||n<1)returnNULL;node*p,*q;p=q=head;while(q!=NULL&&n--){q=q->next;}if(n>=0)returnNULL;while(p!=NULL&&q!=NULL){p=p->next;q=q->next;}returnp;}
方法二:可以先计算出节点个数,即从头到尾遍历一次链表,得到个数m,那么倒数第n个元素也即第m-n+1个元素.与方法一是同样的思维,只是具体操作方式不同,代码略.
JAVA代码:
LinkedListNodenthToLast(LinkedListNodehead,intn){if(head==null||n<1){returnnull;}LinkedListNodep1=head;LinkedListNodep2=head;for(intj=0;j<n-1;++j){//skipn-1stepsaheadif(p2==null){returnnull;//notfoundsincelistsize<n}p2=p2.next;}while(p2.next!=null){p1=p1.next;p2=p2.next;}returnp1;}