反转一个带有随机指针的链表

Question

我最近遇到了一个有趣的问题：

"考虑一个链表，每个节点除了有 'next' 指针外，还有一个 'random' 指针。'random' 指针指向链表上的某个随机节点。它也可能指向 NULL。为了简化问题，没有两个 'random' 指针会指向同一个节点，但是超过1个节点的 'random' 指针可以指向 NULL。

现在我们需要翻转链表中所有指针（包括 'next' 和 'random'）。限制条件是解决方案必须是 O(1) 空间复杂度（可以创建固定数量的新节点，但不应与链表长度成比例）"

我花了很多时间思考这个问题。 我并不确定这是否真的可能。

- arun_suresh

Answer 1

你还需要考虑随机链形成一个（简单）环的情况。你可以通过对链进行线性遍历来检测循环；如果循环中有偶数个节点，则需要再次反转。

- P.A.Kaya

Answer 2

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

反转下一个指针：

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)，很可能不是最快的解决方案。尽管如此，它确实使用了恒定的空间（虽然甚至可以通过内联和积极的变量共享来进一步减少空间占用）。

- Konstantin Tarashchanskiy

---

谢谢你的回答。但是，我有一个问题..如何避免重新反转随机链？假设您已经反转了一个随机链，该链出现在主列表的开头某处。后来，在遍历主列表时，您遇到了一个节点，该节点是您已经反转过的早期随机链的成员..为此，您需要额外的记录..如何在不使用额外存储的情况下跟踪它？ - arun_suresh

@arun_suresh 你说的没错，存在双重反转的风险，但不是你所期望的那样。下一个指针反转是可以的，因为你只在第一个函数中反转了下一个指针。你在之后反转了随机指针并保留了下一个指针，因此不存在交叉污染的风险。此外，由于没有两个节点指向同一个随机指针，这也是安全的。唯一的风险是链的头部比尾部更靠后，因此当我们到达尾部时首先将其反转，然后再到达新的尾部时再次反转。 - Konstantin Tarashchanskiy

好的，是的，简单的解决方案：让新链尾不以NULL结尾，而是以一个特殊值结尾，然后在我们完成反转后清理它们。我会编辑问题。 - Konstantin Tarashchanskiy

Answer 3

< p >（扩展Konstantin N.的答案） < p >为了确保您不会重新反转任何内容，您可以逐个节点从左到右遍历列表，并存储上一个检查过的节点的索引。

lastIndex <- 0
cur <- head

while cur.next not null:
    if cur.random is null:
        randomHead <- # use Konstantin N's findParent helper
        if get_index(randomHead) < lastIndex:
            # we've already examined it
        else:
            # Konstantin N's reverseRandom()
    cur <- cur.next
    lastIndex <- lastIndex + 1

// helper to find node index
get_index(node):
    cur <- head
    ret <- 0

    while cur.next not null:
        if cur == node:
            ret <- ret + 1
    return ret

- Wonerol

---

我认为这并不能解决我的代码问题（请看我的评论）。假设我们有一个随机链1>2>3>4。它应该被反转为4>3>2>1，但当我们到达节点4时，lastIndex变量被设置为3，而randomHead是2，所以我们会忽略它。 - Konstantin Tarashchanskiy

Answer 4

以下是我尝试使用O(1)解空间解决方案并具有O(n)时间复杂度的结果。

static Node<E> reverseList(Node<E> head) {
  if(head == null || head.next == null) {
    return head;
  }

  Node<Integer> current = head;
  Node temp = null;

  // Reverse an existing Linked list.
  while(current != null) {
    Node previousNext = current.next;
    current.next = temp;
    temp = current;
    current = previousNext;
  }

  reversedHead = temp;
  while(temp != null) {
    if(temp.jump != null) { 
      Node jumpTemp = temp.jump; 
      jumpTemp.jump = temp;  
      temp.jump = null; 
    }
    temp = temp.next;
  }

  return reversedHead;
}

- Eternalcode