5

所以我从考试中得到了这个问题。

如何从单链表的尾部获取第 n 个节点？

每个节点都有一个值和一个下一个（指向下一个值的指针）。我们得到这个：

getNodeFromTail(Node head, int x) {

}

所以我这样做的方法是通过遍历一次来找到列表的长度。然后再去获取 (length - x) 节点。所以总共有2次遍历。

getNodeFromTail(Node head, int x) {
    int length = 0;
    Node headdupe = head;
    while (headdupe.next != NULL) {
         headdupe = headdupe.next;
         length++;
    }
    int a = length--;
    for (int y = 0; y < a; y++) {
         head = head.next;
    }
    return head;
}

这是对的，但还有一个额外的问题是问我们是否可以做同样的事情，但只能遍历一次。考试的时候想不出来，后来想了一个办法，但又不太确定。

我可以制作一个长度为 x 的 ArrayList。然后每次我运行while循环时，我都会在数组的顶部添加一个元素，向下级联并启动数组的最后一个元素。然后当头部命中 null 时，返回数组 [x-1] 处的节点。

这是正确的吗？有更好的解决方案吗？

4

6 回答 6

8
  1. 制作2个指向第一个节点的指针
  2. 前进一个指针x
  3. 并排推进两个指针，直到列表中更远的指针到达末尾。
  4. 您的指针进一步向后指向x最后一个元素。
于 2013-09-23T19:49:35.877 回答
3

我会做以下事情：

保持一个大小的循环缓冲区，x并在遍历列表时将节点添加到其中。当您到达列表的末尾时，尾部的第 x 个等于循环缓冲区中的下一个条目。

在伪代码中：

Node getNodeFromTail(Node head, int x) {
  // Circular buffer with current index of of iteration.
  int[] buffer = new int[x];
  int i = 0;

  do {
    // Place the current head in its position in the buffer and increment
    // the head and the index, continuing if necessary.
    buffer[i++ % x] = head;
    head = head.next;
  } while (head.next != NULL);

  // If we haven't reached x nodes, return NULL, otherwise the next item in the
  // circular buffer holds the item from x heads ago.
  return (i < x) ? NULL : buffer[++i % x];
}

此解决方案需要额外x的内存，并且是使用运行时间换取内存的经典示例。

注意：如果输入列表小于x未定义，该怎么办。

于 2013-09-23T19:44:33.850 回答
2

保持 2 个指针，前进第一个指向第 N 个节点的指针现在指向第二个指向头的指针保持前进两个指针现在直到第一个到达结束第二个指针现在指向倒数第 N 个

案例列表中的额外注意事项少于 N 个元素

于 2013-09-23T19:48:56.500 回答
1

您可以在不遍历两次或递归的情况下做到这一点。请参阅以下内容：

int getNodeFromTail(Node head, int position)
{
    if (head == NULL)
      return 0;

      // 2 pointers needed
      Node first = head;
      Node sec = head;

      for(int i = 0; i < position; i++)
        sec = sec.next;

      while (sec.next != NULL)
      {
        sec = sec.next;
        first = first.next;
      }

      return first;
}
于 2014-01-08T12:35:17.797 回答
1

您不需要 2 个效率低下的循环，只需使用 2 个指针和一个计数器：

Node getNodeFromTail(Node head, int x)
{
    Node p = head;
    Node q = head;

    int diff = 0;

    while (p.next != NULL)
    {
        p = p.next;

        if (diff >= x)
            q = q.next;
        else
            diff++;
    }
    return q;
}
于 2015-07-02T16:44:06.860 回答
0

这是最简单的解决方案

static int getNodeNoStack(ListNode head, int k) {
    ListNode result = head;
    int count = 0;
    while(head.next != null) {
        if(count < k) {
            count++;
        } else {
            result = result.next;
        }
        head = head.next;
    }
    return result.val;
}

您只需将指针“结果”保持在距离 head 遍历整个列表直到结束的 k 处。一旦 head 位于末尾，则结果指针将位于 tail 的第 k 个位置

于 2020-07-01T19:23:46.537 回答