我正在考虑在Algo上找到Singly Link List中的最后第三个元素，我自己想出了一个（有效空间）
使用O（n）时间复杂度[大量空间复杂度]的循环将链表放入ArrayList中
然后找到Arraylist的大小，并在（size-2）索引位置检索元素[必需元素]如果我的算法有意义，请指导我
仅供参考
我搜索的其他是：放两个指针，第一个指针放在第一个元素上，第二个指针放第三个元素上并平行移动
当第二个指针到达LinkList的末尾时，检索第一个指针所指向的节点[必需节点]
- 使用两个指针：
pointer-1和pointer-2 -
使CCD_ 3指向单链表中的第三个节点。
pointer-1 = node1->next->next; // point to 3rd nd node1-->node2-->node3-->node4---> ...... -->node-last ^ | pointer-1 -
现在将
pointer-2点设置为第一个节点pointer-2 = node1; // point to 1st nd node1-->node2-->node3-->node4---> ...... -->node-last ^ ^ | | pointer-2 pointer-1 -
现在，在一个循环中的链表中旅行，直到
pointer-1指向最后一个节点，在循环中也更新指针-2（每次到自己的下一个节点）while (pointer-1->next!=NULL){// points to last node pointer-1 = pointer-1 -> next; pointer-2 = pointer-2 -> next; } When loop ends pointer-1 points to last-node, pointer-2 points to third last node1-->node2-->........ ->node-l3-->node-l2-->node-last ^ ^ | | pointer-2 pointer-1
它适用于O（n）次，其中n是链表中的节点数。
由于链表是单独链接的，您需要从头到尾遍历它才能知道从第三个到最后一个元素是什么，因此os O(n)时间是不可避免的（除非您在链表中保留指向从第三到最后一元素的指针）。
你的2个指针的想法，将使用恒定的空格。这可能是更好的选择，因为创建ArrayList会有更多的开销，并占用更多的空间。
获取两个指针。pA，pB将pA移动到3个元素前进，将pB移动到头部：
1->2->3->4-> .... ->99->100
| |
pB pA
之后，在同一个循环中移动两个指针，直到pA到达最后一个元素。
此时，pB将指向最后一个第三元素
1->2->3->4-> .... ->98->99->100
| |
pB pA
编辑时间：遍历将是一个：
while(pA->next!=null){
pA = pA->next;
pB = pB->next;
}
这里pB将是最后一个的第三个
即使是O（n），解决此问题的另一种视图
创建一个空数组（n），在0处启动一个指向该数组的指针，并从链表的开头开始。每次访问节点时，都将其存储在数组的当前索引中，并推进数组指针。不断填充数组中的节点，当您到达数组末尾时，请从头开始，以便覆盖。现在，一旦您结束了列表的最后一个末尾，指针从末尾起第n个elemtn：）
在实践中，Java LinkedList会跟踪其大小，因此您可以直接转到"list.get（list.size（）-2）"，但对于构建的链表，我会执行以下操作：
保留一个由3个值组成的数组。遍历列表时，在array[i%3]处添加更新值。当没有更多值时，返回array[(i-2)%3]处的值。
我要做的第一件事是让您重新考虑使用单链表。为什么不将数据存储在ArrayList中？它可以做你想做的一切，而且它是一个内置的，所以与大多数人写的相比，它相对高效。
如果您已经绑定并决定使用链表，我建议您保留一个指向倒数第三个元素（tle）的直接指针。插入很容易——如果它们出现在tle之前，什么也不做；如果在之后，将tle指针前进到tle的下一个指针。拆迁更麻烦，但可能不是大多数时候。如果移除发生在tle之前，那么它仍然是tle。令人讨厌的情况是，如果要删除的元素是tle或更高版本，在这种情况下，您可以从一开始迭代，直到当前节点的next（）引用是tle。当前节点将成为新的tle，然后可以继续删除。由于只有三个节点可以调用这一级别的工作，所以如果列表相当大，那么大多数情况下您可能都会做得很好。
最后一个选择是，如果经常出现从末尾删除的情况，则从后到前维护您的列表。然后，出于维护目的，tle变为从前面起的第三个。
//We take here two pointers pNode and qNode both initial points to head
//pNode traverse till end of list and the qNode will only traverse when difference
// between the count and position is grater than 0 and pthNode increments once
// in each loop
static ListNode nthNode(int pos){
ListNode pNode=head;
ListNode qNode=head;
int count =0;
while(qNode!=null){
count++;
if(count - pos > 0)
pNode=pNode.next;
qNode=qNode.next;
}
return pNode;
}