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

问题描述

以下函数试图找到单向链表的 nth 到 last 元素.

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

例如:

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

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

推荐答案

您的算法首先创建对链表中相距 N 个节点的两个节点的引用.因此，在您的示例中，如果 N 为 7，那么它会将 p1 设置为 8，将 p2 设置为 4.

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.

然后它将每个节点的引用推进到列表中的下一个节点，直到 p2 到达列表中的最后一个元素.同样，在您的示例中，这将是 p1 为 5 且 p2 为 10 时.此时，p1 指的是第 N 个到列表中的最后一个元素(根据它们相隔 N 个节点的属性).

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屋！