c++ - 反转具有循环的链表

Question

如果链表有环(即如果最后一个节点链接到中间的节点)，我们如何反转链表？

好吧，我看到了 solutions in here 中的一个和 here检测链表中的循环就是将其反转。我的疑问是——如果你不知道它在哪里结束，怎么可能反转一个链表。甚至如何反转具有循环的链表？

Answer 1

嗯，首先，您需要定义“反向”在此上下文中的含义。大概，你需要做的是

(1) 找到使之成为循环的链接

(2) 断开那个链接

(3) 然后以某种方式反转列表。

有效地执行它意味着找到一些有效的方法来识别循环。但是如果我们假设一个堆栈有一个操作来判断一个节点是否已经存在，那么您可以将节点插入堆栈，检查直到您给出一个您已经看到的节点的链接。然后弹出堆栈，瞧您得到了倒序的列表。

在伪代码中，你需要一个带有 isIn 操作的栈

   stack:
     init()
     push(node)
     pop() returns node
     isIn(node) returns Boolean

然后做类似的事情

 do
    get next node
    if node isIn stack
    then
       while stack not empty
           pop node
       break
    else
       push node in stack
    fi
 od