找出鏈表倒數第n個節點元素的二個辦法。本站提示廣大學習愛好者：（找出鏈表倒數第n個節點元素的二個辦法）文章只能為提供參考，不一定能成為您想要的結果。以下是找出鏈表倒數第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; }
