一尘不染

如何从单链列表的末尾找到第n个元素?

algorithm

下面的函数试图寻找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;
}

阅读 239

收藏
2020-07-28

共1个答案

一尘不染

您的算法通过首先创建对链表中两个节点(相距N个节点)的引用来工作。因此,在您的示例中,如果N为7,则它将p1设置为8,p2设置为4。

然后它将每个节点引用前进到列表中的下一个节点,直到p2到达列表中的最后一个元素。同样,在您的示例中,这将是p1为5且p2为10时。在这一点上,p1指的是列表中最后一个元素的第N个元素(通过属性,它们相距N个节点)。

2020-07-28