如何从单链表的末尾find第n个元素？

下面的函数试图find单向链表的nth元素。

例如：

如果元素是8->10->5->7->2->1->5->4->10->10那么结果是7th到最后一个节点是7 。

任何人都可以帮助我这个代码如何工作，或者有更好更简单的方法吗？

 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; } 

Answer 1

您的algorithm通过首先创build链接列表中相隔N个节点的两个节点的引用。 因此，在你的例子中，如果N是7，那么它将把p1设置为8，将p2设置为4。

然后，它会将每个节点引用推进到列表中的下一个节点，直到p2到达列表中的最后一个元素。 再次，在你的例子中，这将是当p1是5，p2是10时。在这一点上，p1指的是列表中的最后一个元素的第N个（通过它们相隔N个节点的属性）。

Answer 2

这个algorithm的关键是首先设置两个指针p1和p2分开n-1节点，所以我们希望p2指向从列表开始的(n-1)th节点，然后我们移动p2直到达到last列表的节点。 一旦p2到达列表的末尾， p1将指向列表末尾的第n个节点。

我把这个解释作为评论。 希望能帮助到你：

 // Function to return the nth node from the end of a linked list. // Takes the head pointer to the list and n as input // Returns the nth node from the end if one exists else returns NULL. LinkedListNode nthToLast(LinkedListNode head, int n) { // If list does not exist or if there are no elements in the list,return NULL if (head == null || n < 1) { return null; } // make pointers p1 and p2 point to the start of the list. LinkedListNode p1 = head; LinkedListNode p2 = head; // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially // so we want p2 to point to the (n-1)th node from the start of the list // then we move p2 till it reaches the last node of the list. // Once p2 reaches end of the list p1 will be pointing to the nth node // from the end of the list. // loop to move p2. for (int j = 0; j < n - 1; ++j) { // while moving p2 check if it becomes NULL, that is if it reaches the end // of the list. That would mean the list has less than n nodes, so its not // possible to find nth from last, so return NULL. if (p2 == null) { return null; } // move p2 forward. p2 = p2.next; } // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward // till p2 reaches the last node in the list. while (p2.next != null) { p1 = p1.next; p2 = p2.next; } // at this point p2 has reached the last node in the list and p1 will be // pointing to the nth node from the last..so return it. return p1; } 

或者，我们可以将p1和p2设置为n个节点而不是(n-1) ，然后将p2移动到列表的末尾，而不是移动到最后一个节点：

 LinkedListNode p1 = head; LinkedListNode p2 = head; for (int j = 0; j < n ; ++j) { // make then n nodes apart. if (p2 == null) { return null; } p2 = p2.next; } while (p2 != null) { // move till p2 goes past the end of the list. p1 = p1.next; p2 = p2.next; } return p1; 

Answer 3

你对这种方法有什么看法？

1. 计算链表的长度。
2. 来自head的实际节点索引=链接列表长度 – 给定索引;
3. 编写一个从头开始的函数，并获取上述索引处的节点。

Answer 4

 //this is the recursive solution //initial call find(HEAD,k); // main function void find(struct link *temp,int k) { if( temp->next != NULL) find( temp->next, k); if((c++) == k) // c is initially declared as 1 and k is the node to find from last. cout<<temp->num<<' '; } 

Answer 5

由于这听起来像功课，我宁愿帮助你自己而不是提供一个实际的解决scheme。

我build议你在一些小样本数据集上运行这个代码。 使用你的debugging器一步一步地运行（你可以在函数的开始处设置一个断点）。 这应该给你一个代码的工作原理。

你也可以通过Console.WriteLine()来输出感兴趣的variables。

Answer 6

这个问题的另一个解决scheme。 虽然时间复杂度保持不变，但这个代码在单一循环中实现了解决scheme。

 public Link findKthElementFromEnd(MyLinkedList linkedList, int k) { Link current = linkedList.getFirst();//current node Link currentK = linkedList.getFirst();//node at index k int counter = 0; while(current.getNext()!=null) { counter++; if(counter>=k) { currentK = currentK.getNext(); } current = current.getNext(); } //reached end return currentK; } 

Answer 7

只需在线性时间内倒转链表，find第k个元素。 它仍然在线性时间运行。

Answer 8

这里已经有很多答案，但是他们都是按照顺序或者并行的方式遍历列表，或者使用大量额外的存储空间。

你可以使用常量额外的空间来做这个事情，只需要一次（加一点点）：

 Node *getNthFromEnd(Node *list, int n) { if (list == null || n<1) { return null; //no such element } Node *mark1 = list, *mark2 = list, *markend = list; int pos1 = 0, pos2 = 0, posend = 0; while (markend!=null) { if ((posend-pos2)>=(n-1)) { mark1=mark2; pos1=pos2; mark2=markend; pos2=posend; } markend=markend->next; ++posend; } if (posend<n) { return null; //not enough elements in the list } //mark1 and mark2 are n-1 elements apart, and the end is at least //1 element after mark2, so mark1 is at least n elements from the end while((posend - pos1) > n) { mark1 = mark1->next; ++pos1; } return mark1; } 

这个版本使用2个额外的指针小于N+n遍历，其中N是列表的长度， n是参数。

如果你使用M额外的指针，你可以把它指向N+ceil(n/(M-1)) （你应该把它们存储在一个循环缓冲区中）

Answer 9

你可以循环访问链表并获取大小。 一旦你有了大小，你就可以在2n中find第n个词，它仍然是O（n）。

 public T nthToLast(int n) { // return null if linkedlist is empty if (head == null) return null; // declare placeholder where size of linkedlist will be stored // we are hoping that size of linkedlist is less than MAX of INT int size = 0; // This is O(n) for sure Node i = head; while (i.next != null) { size += 1; i = i.next; } // if user chose something outside the size of the linkedlist return null if (size < n) return null; // This is O(n) if n == size i = head; while(size > n) { size--; i = i.next; } // Time complexity = n + n = 2n // therefore O(n) return i.value; } 

Answer 10

在这里我有我的recursion解决scheme在另一个线程在StackOverflow

Answer 11

不，你不知道链表的长度…你将不得不经过一次才能得到喜欢的列表的长度，所以你的方法是有效率的;

Answer 12

recursion解决scheme：

 Node findKth (Node head, int count, int k) { if(head == null) return head; else { Node n =findKth(head.next,count,k); count++; if(count == k) return head; return n; } } 

Answer 13

我们在这里采用两个指针pNode和qNode，这两个起始点都是头qNode。 然后，遍历到列表的最后，只有在计数和位置之间的差值大于0时，pNode才会遍历，并且pthNode在每个循环中递增一次。

 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; } 

Answer 14

 public int nthFromLast(int n){ Node current = head; Node reference = head; for(int i=0;i<n;i++){ reference=reference.getNext(); } while(reference != null){ current = current.getNext(); reference = reference.getNext(); } return current.getData(); } 

Answer 15

使用两个指针pTemp和NthNode。 最初，都指向列表的头节点。 只有在pTemp进行了n次移动之后，NthNode才开始移动。 从这两个向前移动，直到pTemp到达列表的末尾。 结果NthNode指向链表尾部的第n个节点。

 public ListNode NthNodeFromEnd(int n){ ListNode pTemp = head, NthNode = null; for(int count=1; count<n;count++){ if(pTemp!=null){ pTemp = pTemp.getNext(); } } while(pTemp!=null){ if(NthNode==null){ NthNode = head; } else{ NthNode = NthNode.getNext(); } pTemp = pTemp.getNext(); } if(NthNode!=null){ NthNode = NthNode.getNext(); return NthNode; } return null; } 

参考TextBook：“Java中的数据结构和algorithm变得简单”

Answer 16

要理解这个问题，我们应该用一个测量例子来做一个简单的比喻。 比方说，你必须find距离中指1米远的地方，你会怎么测量？ 你只需要拿一把长度为1米的尺子，把这个尺子的顶端放在你的中指尖上，这个尺子的底端距离你的中指的正上方1米，手指。

我们在这个例子中做的是相同的，我们只需要一个n元素宽的帧，我们要做的就是把帧放到列表的末尾，这样帧的起始节点就是n元素， th元素到列表的末尾。

这是我们的列表，假设我们在列表中有M个元素，而我们的N元素的框架宽;

 HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M) <-- Frame --> 

然而，我们只需要帧的边界，因此帧的结束边界就会正好离开帧的起始边界（N-1）个元素。 所以只能存储这些边界元素。 我们称他们为A和B;

 HEAD -> EL(1) -> EL(2) -> ... -> EL(M-1) -> EL(M) A <- N-Element Wide-> B 

我们要做的第一件事是findB，这是框架的结尾。

 ListNode<T> b = head; int count = 1; while(count < n && b != null) { b = b.next; count++; } 

现在b是数组的第n个元素，而a位于HEAD上 。 所以我们的框架是设置的，我们要做的是逐步增加两个边界节点，直到b到达列表的最后，其中a将是第n个元素;

 ListNode<T> a = head; while(b.next != null) { a = a.next; b = b.next; } return a; 

要收集所有的东西，用HEAD检查，N <M（其中M是列表的大小）检查和其他东西，这里是完整的解决方法;

 public ListNode<T> findNthToLast(int n) { if(head == null) { return null; } else { ListNode<T> b = head; int count = 1; while(count < n && b != null) { b = b.next; count++; } if(count == n && b!=null) { ListNode<T> a = head; while(b.next != null) { a = a.next; b = b.next; } return a; } else { System.out.print("N(" + n + ") must be equal or smaller then the size of the list"); return null; } } } 

Answer 17

您也可以使用散列表来解决上述问题。散列表的条目是节点的位置和节点的地址。 所以如果我们想从结尾find第n个节点（这意味着从第一个m-n + 1开始，其中m是节点数目）。现在，当我们input哈希表项时，我们得到节点的数目。步骤如下：

1.遍历每个节点并在哈希表中做相应的条目。

2.查找散列表中的m-n + 1节点，我们得到地址。

时间复杂度是O（n）。

Answer 18

我认为问题代码中有一个缺陷，我不知道它是否从一本书中被采取了这是怎么可能的…它可以正确执行，但代码在逻辑上是不正确的。 在for循环中… if条件应该检查p2->next ! = NULL p2->next ! = NULL

  for (int j = 0; j < n - 1; ++j) { // skip n-1 steps ahead if (p2->next == null) { return null; // not found since list size < n } 

…rest是好的，解释已经给代码转移p2 (n-1)位置前进到p1 ，然后在while循环它将它们同时移动，直到p2->next达到结束..随意告诉你是否发现我的答案不正确

Answer 19

职业杯书中给出的问题稍有不同。 它说find单向链表的倒数第n个元素。

这是我的代码：

  public void findntolast(int index) { Node ptr = front; int count = 0; while(ptr!=null) { count++; if (count == index) { front = ptr; break; } ptr = ptr.next; } Node temp=front; while(temp!=null) { Console.WriteLine(temp.data); temp=temp.next; } } 

Answer 20

你可以使用额外的数据结构..如果是的话，这将是简单的…开始推动所有的节点到堆栈，保持一个计数器popup它。 按照你的例子，8-> 10-> 5-> 7-> 2-> 1-> 5-> 4-> 10-> 10开始读链表，并开始推动节点或节点 – >数据到一个堆栈。 所以堆栈看起来像顶部 – {10,10,4,5,1,2,7,5,10,8} – 底部。

现在开始从堆栈顶部popup，维持一个计数器= 1，每次你popup时，将计数器加1，当你到达第n个元素（在你的例子第7个元素）停止popup。

注意：这将以相反的顺序打印或检索数据/节点

Answer 21

这里是使用2指针方法的代码:( 源 ）

指针缓慢，速度更快

 struct node { int data; struct node *next; }mynode; mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/) { mynode *ptr1,*ptr2; int count; if(!head) { return(NULL); } ptr1 = head; ptr2 = head; count = 0; while(count < n) { count++; if((ptr1=ptr1->next)==NULL) { //Length of the linked list less than n. Error. return(NULL); } } while((ptr1=ptr1->next)!=NULL) { ptr2=ptr2->next; } return(ptr2); } 

recursion

 node* findNthNode (node* head, int find, int& found){ if(!head) { found = 1; return 0; } node* retval = findNthNode(head->next, find, found); if(found==find) retval = head; found = found + 1; return retval; } 

---

Answer 22

我的方法，我认为是简单的，并且具有时间复杂度O（n）。

步骤1：首先获取节点数量。 运行从第一个节点到最后一个节点的for循环

步骤2：一旦你有了计数，应用简单的math，例如，如果我们已经find第七个节点到最后一个节点，并且所有节点的计数是12，则（count-index）-1将给出第k个节点，直到你将不得不遍历它，它将是最后一个节点的第n个节点。 在这种情况下（12-7）-1 = 4

如果元素是8-> 10-> 5-> 7-> 2-> 1-> 5-> 4-> 10-> 10，那么结果是第7个到最后一个节点是7，这只不过是第4个节点开始。

Answer 23

在Java中，我将使用 –

 public class LL { Node head; int linksCount; LL(){ head = new Node(); linksCount = 0; } //TRAVERSE TO INDEX public Node getNodeAt(int index){ Node temp= head; if(index > linksCount){ System.out.println("index out of bound !"); return null; } for(int i=0;i<index && (temp.getNext() != null);i++){ temp = temp.getNext(); } return temp.getNext(); } } 

Answer 24

没有人注意到，如果n大于LinkedList的长度，Jonathan的版本将会抛出一个NullPinterExceptionexception。 这是我的版本：

 public Node nth(int n){ if(head == null || n < 1) return null; Node n1 = head; Node n2 = head; for(int i = 1; i < n; i++){ if(n1.next == null) return null; n1 = n1.next; } while (n1.next != null){ n1 = n1.next; n2 = n2.next; } return n2; } 

我在这里只做了一些小改动：当节点n1前进时，而不是检查n1是否为空，我检查天气n1.next是否为null，否则在while循环中n1.next将抛出NullPinterException。

Answer 25

这里是从Linklist中find第n个孩子的C＃版本。

 public Node GetNthLast(Node head, int n) { Node current, nth; current = nth = head; int counter = 0; while (current.next != null) { counter++; if (counter % n == 0) { for (var i = 0; i < n - 1; i++) { nth = nth.next; } } current = current.next; } var remainingCounts = counter % n; for (var i = 0; i < remainingCounts; i++) { nth = nth.next; } return nth; } 

Answer 26

根据内存成本容差（在这个解决scheme中的O（k）），我们可以分配一个长度为k的指针数组，并在遍历链表时用节点填充为圆形数组。

当我们完成遍历链表时，数组的第一个元素（只要确保正确计算0-索引，因为它是一个圆形数组），我们将得到答案。

如果数组的第一个元素为null，那么我们的问题就没有解决的办法了。