算法找出指针M节点步骤尾单链表 [英] Algorithm to Find the pointer to the Node M Steps to Tail in a Singly Linked List

问题描述

假设有一个单向链表，其长度是未知的。我们希望找到具有M步骤尾节点

Suppose there is a singly linked list whose length is unknown. We want to find the node with M steps to the tail.

例如，在单独的列表是这样的： （A） - >（B） - >（C） - >（X） - >（Y） 和M = 2。 然后输出应为指针至（C）。

For example, the singly list is like this: (A)->(B)->(C)->(X)->(Y) and M = 2. Then the output should be pointer to (C).

当面对这个测验，我的第一反应就是遍历链表得到长度N.然后遍历单独的第二次，但只能向前NM-1的步骤。时间复杂度为O（n）和空间复杂度为O（1）。

When confronting this quiz, my first reaction is to traverse the singly linked list to get the length N. Then traverse the singly the second time, but only forward N-M-1 steps. The time complexity is O(n) and space complexity is O(1).

然后，我面临的挑战是找到一个解决办法做到这一点在一个横向的方式。解决的办法是有两个指针。第二个指针是第一个指针我身后的步骤。这两个指针向前移动在同样的速度。当第一指针到达尾部，所述第二指针是结果。

Then, I'm challenged to find a solution to do it in one-traverse way. The solution is to have two pointers. The second pointer is M steps behind the first pointer. These two pointers move forward at same pace. When the first pointer reaches tail, the second pointer is the result.

在这个问题上深刻反思后，我真的不相信第二个棘手的解决方案比第一个优越。它是一个移动，但它也涉及2 * NM指针赋值。

After deep reflection on this question, I really don't believe the second "tricky" solution is superior than the first one. It is one-traverse, but it also involves 2*N-M pointer assignments.

这个问题的任何想法？ 是否有任何其他的解决方案，真正更快？

Any thought about this question? Is there any other solution that is really faster?

推荐答案

您应该使用循环缓冲区

分配的M + 1的指针数组，并填写（一模m + 1）个指针通过列表中的每个节点。当你到达终点，看回来了数组（环绕着如果需要）。

Allocate an array of M + 1 pointers, and fill in the (i mod M + 1)th pointer for each node through the list. When you reach the end, look M back in the array (wrapping around if you need to).

这样的话，你只能有N个写！

That way, you only have N writes!

下面是一个黑客的工作示例程序用C ++

Here's a hack job sample program in c++

node* get_Mth_from_end(node* head, int m)
{
  int pos = 0;
  node** node_array = new node*[m + 1];
  node_array[0] = head;
  while (node_array[(pos + 1) % (m + 1)] = node_array[pos % (m + 1)]->next)
     pos++;
  if (pos < m)
  {
     delete[] node_array;
     return NULL;
  }
  pos = pos - m;
  if (pos < 0)
     pos = pos + m + 1;
  node* retval = node_array[pos];
  delete[] node_array;
  return retval;
}

这应该由1错误被检查过。 我的指针语法可能有点过了，但是这个想法是存在的。

This should be checked for off by 1 errors. My pointer syntax may be a little off too, but the idea is there.

这篇关于算法找出指针M节点步骤尾单链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！