雙指針。先讓一個指針順著鏈表走n次，然後再讓一個指針從頭開始走。然後兩個指針同時順鏈表走，直到第一個指針走到鏈表尾部，此時第二個指針的位置就是倒數第n個節點。

1.單鏈表:先遍歷一遍，從遍歷的內容獲取。

2.雙向鏈表:遍歷到最後，往回倒n個

3.循環單鏈表:跟單鏈表一樣

4.循環雙鏈表:往後遍歷n個

雙指針

第一個指針走n步

然後第二個指針從頭開始，兩個指針一起走，

當第一個指針指到最後的時候，第二個指針正好指向倒數n個節點

單鏈表的話，一般用雙指針是最優解：O(1)空間，O(n)時間。

但我有一個騷操作——遞歸。O(2n)時間，O(1)空間（不考慮調用棧。考慮的話則是O(n)）

考慮單鏈表是一棵每個結點只有右（或者左）子樹的二叉樹，那麼可以使用後根遍歷的方式來處理。代碼如下：

private static void getNthFromLast(ListNode head, ListNode[] ret, int[] n) {
if (head == null || ret[0] != null) {
return;
}
getNthFromLast(head.next, ret, n);
if (—-n[0] == 0) {
ret[0] = head;
}
}

public static ListNode getNthFromLast(ListNode head, int n) {
if (n &<= 0 || head == null) { return null; } ListNode[] ret = new ListNode[1]; getNthFromLast(head, ret, new int[]{n}); return ret[0]; }

姑且嘗試解答這個問題，僅供參考！

什麼是鏈表？

鏈表是一種常見的重要的數據結構。它是動態地進行存儲分配的一種結構。它可以根據需要開闢內存單元。鏈表有一個「頭指針」變數，以head表示，它存放一個地址。該地址指向一個元素。鏈表中每一個元素稱為「結點」，每個結點都應包括兩個部分：一為用戶需要用的實際數據，二為下一個結點的地址。因此，head指向第一個元素：第一個元素又指向第二個元素；……，直到最後一個元素，該元素不再指向其它元素，它稱為「表尾」，它的地址部分放一個「NULL」（表示「空地址」），鏈表到此結束。

8種鏈表

節點結構

typedef struct SListNode

{ SDataType _data;

struct SListNode* _PNext;

}Node,*PNode;

如何獲取倒數第n個元素（以非循環單鏈表為例）？

① 首先獲取到總的元素個數為 m

方法：從表頭開始遍歷，直到最後一個節點。

② 然後用 m -n +1, 得到的就是從表頭開始的元素，也就是相當於倒數第n個元素。

如下圖：

③程序實現

求總的節點數 m ：
int m = 0;
struct student *p = head;
if(head != NULL)
{
do
{
m++;
p = p-&>next; //移到下一個節點
}
while (p != NULL);
}

再正向遍歷
int i = 0;
struct student *p = head;
if(head != NULL n &<= m) { do { i++; if(i == m-n+1) { printf("%d ", p-&>_data);
break;
}
p = p-&>next; //移到下一個節點
}
while (p != NULL);

}

逆向的話，可能需要雙向鏈表了，比較方便。

代碼比較草稿，記事本寫的，僅供參考。

謝邀，我想了一下，大概有如下幾種方式：

  1. 迭代整個鏈表，把每個元素加入到棧中，最後一次從上往下從棧中取出n個元素即可
  2. 換個思路，反轉鏈表，然後從前往後數n個元素即可
  3. 迭代一遍計算鏈表的長度len，然後計算出len-n，然後第len-n+1個元素即是我們想要的元素
  4. 使用雙指針，指針a跟指針b，指針a先向前走n步，然後a跟b開始同步移動，當a走到末尾時，b的下一個元素即是我們要找的元素

再次謝邀，我平時也有在整理一些演算法相關的思路跟套路，有興趣的可以看看我的專欄：

一道題做一宿?

zhuanlan.zhihu.com圖標

雙指針第一個指針先走n步就行了，我記得leetcode上有原題

pointer1=head
pointer2=head
p1_pos = 0
# You can use while p1_pos &< n and pointer1 to prevent from n &> listnode_length
while p1_pos &< n: pointer1 = pointer1.next p1_pos += 1 # after this while loop, pointer1 is in nth position, now start to move both pointer1 and 2 together # if next element is not None while pointer1.next: pointer1 = pointer1.next pointer2 = pointer2.next # if pointer1 reaches to the end, pointer2 is in listnode_length - n pos return pointer2

沒用ide,直接在知乎回答框寫的python代碼,縮進之類的東西可能有問題.

也懶得寫def結構什麼的了..反正python是最像偽代碼的代碼, head是首節點. node.next是當前節點的下一個節點

雙指針很簡單啊

先讓第一個指針提前走n步

然後第一、二個指針再同時走，直到指針一到達鏈表末尾，這時候指針二的位置就是倒數第n個元素的位置

推薦閱讀：
相關文章