颠倒有循环的链表

如果它有一个循环（即，如果最后一个节点链接到中间的一个节点），我们如何反转链表？颠倒有循环的链表

嗯，我看到solutions in here之一，here来检测一个循环，一个链表扭转它。我的疑问是 - 如果你不知道它在哪里结束，怎么可能反转链表。怎么能甚至扭转一个有循环的链表？

2012-03-02 Sharat Chandra

由于这只发生在面试问题和家庭作业中，如果情况如此，请考虑使用家庭作业标记标记这个问题？如果它是一个真正的应用程序，是逆转一个常见的操作？如果是这样，考虑设置一个关于边缘方向的标志来使O（1）操作反转。 – 2012-03-02 04:47:55

它是否有意义扭转这样的名单？想想看。如果有一个循环，那里至少有一个节点有两个输入箭头。相反的那个需要两个输出箭头，不是吗？反向名单的开始位置在哪里？原来的那个没有结束，所以倒过来的那个没有开始，对吧？它确实有一定的数学意义，并且该操作可以很容易地在Haskell中表达，但不要期望获得结果。 – 2012-03-02 05:02:37

嗯，首先，您需要定义在这种情况下“反向”的含义。也许，你需要做的是

（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

来源

2012-03-02 04:38:26

+1为“需要定义什么”反向“意味着”。 – 2012-03-02 05:06:39

感谢您寻求澄清。这确实是令人困惑的，正是我想知道的 - 一个循环链表如何才能得到尊重。检查我的编辑 – 2012-03-02 06:48:31

问题是，除非明确定义，否则没有人能够回答问题。 – 2012-03-02 14:14:33

我觉得首先你必须定义意味着什么逆转与链表循环。让我们假设你有一个链表：

1->2->3->4->5-| 
    ^  | 
     |-------|

所以，如果通常的名单将打印：12345345345，如果你继续穿越周期假设反向链接的列表将意味着所有的箭都扭转了方向和反向它应该打印54354312

现在你可以做这样的事情：

prev=head; 
curr=head->next; 
while !curr->visited && curr->next!=end 
    tmp=prev 
    prev=curr 
    curr=curr->next 
    prev->next=tmp 
    curr->visited=True

这是伪代码和他们的逻辑可能是小错误，所以不逐字复制，但它是一个基本的想法。

来源

2012-03-02 04:43:49 Sid

如何才能打印反向列表54354312？在节点3之后，5个到来或1个到来。你怎么能得到两个？ – 2012-03-02 05:00:01

是的，我的意思是534534 – Sid 2012-03-02 12:23:44

颠倒有循环的链表

回答

相关问题