找出鏈表倒數第n個節點元素的二個方法

方法一：利用兩個指針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; }