使用具有随机指针的节点反转链接列表

Question

我最近遇到了这个有趣的问题:

"考虑每个节点的链表,除了'下一个'指针还有一个'随机'指针.'随机'指针指向链表上的一些随机的其他节点.它也可能指向NULL.简化事情,没有两个"随机"指针指向同一个节点,但是超过1个节点的随机指针可以指向NULL.

现在我们需要反转Linked列表的所有指针('next'和'random')的方向.约束是解决方案必须是O(1)空间复杂度(可以创建恒定数量的新节点但不与列表的长度成比例)"

我花了很多时间考虑这个.我真的不相信它实际上是可能的.

Answer 1

这是很有可能的。我提出了一个可能不是最佳的解决方案，但表明它可以完成。首先将其分解为两个问题：反转下一个指针和反转随机指针。

反转下一个指针：

node* last = NULL;
node* current = head;
node* next = head->next;
while (current != NULL)
{
  current->next = last;
  last = current;
  current = next;
  if (current != NULL)
    next = current->next;
}
head = last

反转随机列表有点棘手，因为我们没有随机指针链的所有头的列表，但我们可以找到它们的末端（节点将是 NULL 随机指针）。我们需要几个辅助函数来完成它。第一个是反转随机列表。我们主要复制上面的代码。请注意，我们将链的末尾设置为一个特殊值。这阻止我们重新反转列表。请参阅评论中的讨论以获取解释。

node* chainTail = malloc(1); //mallocing here to get a unique pointer
void reverseRandom(node* rhead)
{
  node* last = chainTail;
  node* current = rhead;
  node* next = rhead->random;
  while (current != NULL)
  {
    current->random = last;
    last = current;
    current = next;
    if (current != NULL)
      next = current->random;
  }
}

我们还需要一个辅助函数来查找节点的父节点（如果没有，则返回 NULL）。我们将进行一个愚蠢的线性搜索：

node* findParent(node* target)
{
  node* candidate = head;
  while ((candidate != NULL) && (candidate->random != target))
    candidate = candidate->next;
  return candidate;
}

现在我们只需遍历列表，找到具有随机值 NULL 的任何节点（我们的链尾），找到它们的链头，然后反转链：

node* current = head;  //Current  node in a linear walk looking for chain tails
while (current != NULL)
{
  if (NULL == current->random)
  {
    //current is the tail of a random chain, lets find the head
    node* curr = current; //Current node in the search for the chain hean
    node* parent = findParent(curr);
    while (parent != NULL)
    {
      curr = parent;
      parent = findParent(curr);
    }
    //At this point, curr is the head of the random chain, so reverse it
    reverseRandom(curr);
  }
  current = current->next;
}

//Clean up chainTail pointers
node* current;
for (current = head; current != NULL; current = current->next)
{
  if (current->random == chainTail)
  {
    current->random = NULL;
  }
}
free(chainTail); //Stop a memory leak if this is not a global

标准免责声明：我没有运行此代码。它可能有错误。接近尾声时我开始感到困倦，所以我可能犯了一个逻辑错误，但在我看来这是可行的。

另外，如果您希望将其投入生产，请不要这样做。这段代码的运行时间约为 O(n^3)。这很可能不是最快的解决方案。它确实使用恒定空间（尽管即使如此也可以通过内联和积极的变量共享来减少）。