如何从单向链表末尾查找第n个元素？

Question

以下函数试图查找单向链表的倒数第N个元素。

例如：

如果元素是8->10->5->7->2->1->5->4->10->10，则结果为第7个到最后一个节点是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;
}

- Jony

---

另一个解决方案可能是使用递归，但它比您的算法不太有效。我认为您的算法简单而有效。 - MartyIX

这段代码来自Gayle Laakmann的书，你应该说明一下。 - Jim Balter

https://www.geeksforgeeks.org/nth-node-from-the-end-of-a-linked-list/ 可能会有用。 - Guy Avraham

相关帖子 - 如何从单向链表的末尾找到第n个元素？ - RBT

Answer 1

这个算法的关键在于初始化两个指针p1和p2，使它们相距n-1个节点。我们希望p2指向列表开头的第(n-1)个节点，然后将p2移动到列表的末尾。一旦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;

- codaddict

---

太棒了！这是我见过的最好的解释。非常感谢。 - asgs

Answer 2

你的算法首先要创建两个在链表中相距N个节点的节点的引用。因此，在你的例子中，如果N为7，它将把p1设置为第8个节点，并将p2设置为第4个节点。

然后，它将使每个节点引用逐个向链表中的下一个节点前进，直到p2到达链表的最后一个元素。同样，在你的例子中，这将是当p1是第5个节点，p2是第10个节点时。此时，p1引用的是倒数第N个元素（根据它们相距N个节点的属性）。

- Eric

---

即使按照这种锁步方式执行，它是否类似于对列表进行两次迭代？ 我们可以将每个引用视为一个迭代器，一个遍历到 n，另一个遍历到 n - separation。因此，我们需要的步数与我们使用一个迭代器计数（n 步）并使用另一个迭代器到达位置 n - separation 的节点时一样多。 - Martín Coll

@tinchou：你的建议是一个正确的替代实现，也许更容易理解。这两种实现都是O(n)的，因此它们是类似的。我预计Jonathan问题中的实现会稍微更有效率一些。 - Eric

@tinchou所建议的是递归地到达列表末尾以检索大小_n_，然后再次循环以查找倒数第_k_个元素吗？ - franklin

@franklin 是的，但我会将其描述为迭代到列表的末尾，而不是递归到它。 - Eric

@tinchou，这种锁步方法通常可以更好地利用缓存，因为前指针命中的节点在后指针到达时可能仍然在缓存中。在使用跟踪垃圾收集的语言实现中，这种方法还避免了在操作期间不必要地保持整个列表的活动状态。 - dfeuer

http://code2begin.blogspot.com/2018/04/finding-kth-element-from-end-of-linked.html - M2skills

Answer 3

你认为这个方法怎么样呢。

1. 计算链表的长度。
2. 从头部开始，找到实际节点索引 = 链表长度 - 给定的索引；
3. 编写一个函数从头部开始遍历链表，并获取上述索引处的节点。

- Pritam Karmakar

---

我建议通过保持列表的大小来实现相同的解决方案，这样可以使得它更容易运行。 - Jayasagar

这很好，除了你要遍历两次。一次是为了获取列表的长度（因为没有其他方法可以在不遍历到末尾的情况下知道大小），另一次是为了实际查找你感兴趣的元素。 - asgs

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

- dekontj

Answer 5

您可以遍历链表并获取其大小。一旦您知道了大小，您就可以在2n中找到第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;
}

- Y_Y

Answer 6

这里已经有很多答案了，但它们都需要两次遍历列表（顺序或并行）或使用大量额外的存储空间。您可以在只遍历一次列表（再加上一点点）的情况下，使用恒定的额外空间来完成此操作。

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))（并且你应该将它们存储在循环缓冲区中）

- Matt Timmermans

---

聪明的方法。我第一次尝试思考这个问题时，也考虑过使用循环缓冲区，但是从另一个角度来看。 - Ignacio Hagopian

Answer 7

因为这听起来像是作业，所以我更愿意帮助你自己解决问题而不是直接给出答案。

建议你在一些小的样本数据集上运行此代码。使用调试器逐行运行代码（可以在函数开头设置断点）。这应该能让你了解代码的工作原理。

你还可以使用Console.WriteLine()输出感兴趣的变量。

- mafu

Answer 8

只需在线性时间内反转链表并找到第k个元素。它仍然在线性时间内运行。

- Nithin

Answer 9

你不知道链表的长度... 你需要遍历一次才能获取链表的长度，所以你的方法效率有些低；

- CodeR

Answer 10

这是解决这个问题的另一种方法。虽然时间复杂度仍然相同，但这段代码可以在单个循环中实现解决方案。

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

- sunsin1985

---

这个答案存在缺陷，即在倒数第k个元素不存在的情况下。只需注意列表的长度为N且K>N。在返回语句之前，通过计数器和k之间的简单检查就可以轻松解决这个问题。 :) - Ignacio Hagopian