方法一：利用两个指针p,q，首先将q往链表尾部移动n位，然后再将p、q一起往后移，那么当q达到链表尾部时，p即指向链表的倒数第n个节点。
复制代码 代码如下:
node* find_nth_to_last(node* head,int n) { if(head==null || n<1) return null; node*p,*q; p=q=head; while(q!=null && n--){ q=q->next; } if(n>=0) return null; while(p!=null && q!=null){ p=p->next; q=q->next; } return p; }
方法二:可以先计算出节点个数,即从头到尾遍历一次链表,得到个数m,那么倒数第n个元素也即第m-n+1个元素.与方法一是同样的思维,只是具体操作方式不同,代码略.
java代码:
复制代码 代码如下:
linkedlistnode nthtolast(linkedlistnode head, int n) { if (head == null || n < 1) { return null; } linkedlistnode p1 = head; linkedlistnode p2 = head; for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead if (p2 == null) { return null; // not found since list size < n } p2 = p2.next; } while (p2.next != null) { p1 = p1.next; p2 = p2.next; } return p1; }
