双指针。先让一个指针顺著链表走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个元素的位置

推荐阅读：
相关文章