如何从单链列表的末尾找到第n个元素？ [英] How to find nth element from the end of a singly linked list?

问题描述

以下功能正在尝试查找单链接列表的最后一个元素的 nth 。

例如：

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

有人可以帮助我这个代码是如何工作的，还是有更好的简单的方法？

  LinkedListNode nthToLast（LinkedListNode head，int n）{
 if（head == null || n < 1）{
 return null; 
} 
 
 LinkedListNode p1 = head; 
 LinkedListNode p2 = head; （int j = 0; j  if（p2 == null）{
返回null; //从列表大小< n 
} 
 p2 = p2.next; 
} 
 
 while（p2.next！= null）{
 p1 = p1.next; 
 p2 = p2.next; 
} 
 
 return p1; 
} 
  

解决方案

引用链接列表中的N个节点的两个节点。因此，在您的示例中，如果N为7，则将p1设置为8，将p2设置为4。

然后将每个节点引用到下一个节点列表，直到p2到达列表中的最后一个元素。再次，在你的例子中，这将是当p1是5而p2是10时。在这一点上，p1是指列表中第N个到最后一个元素（由它们是N个节点分开的属性）。 >

The following function is trying to find the nth to last element of a singly linked list.

For example:

If the elements are 8->10->5->7->2->1->5->4->10->10 then the result is 7th to last node is 7.

Can anybody help me on how this code is working or is there a better and simpler approach?

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

解决方案

Your algorithm works by first creating references to two nodes in your linked list that are N nodes apart. Thus, in your example, if N is 7, then it will set p1 to 8 and p2 to 4.

It will then advance each node reference to the next node in the list until p2 reaches the last element in the list. Again, in your example, this will be when p1 is 5 and p2 is 10. At this point, p1 is referring to the Nth to the last element in the list (by the property that they are N nodes apart).

这篇关于如何从单链列表的末尾找到第n个元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！