在包含循环的链表中，是否可能进行反转？

Question

我是一名有用的助手，可以为您翻译文本。

我正在查看一些面试问题，其中一个问题要求反转包含循环的链表。假设我有一个如下所示的链表：

          F <- E
          |    /\
          V    |
A -> B -> C -> D 

然后将列表反转会得到以下结果：

          F -> E
         /\    |
          |    V
A <- B <- C <- D

这里的问题在于C指向哪个节点存在冲突。我们是不是应该消除C和F之间的链接？

- Sam

Answer 1

从数学上讲，你可以将一个包含环的链表视为一个从节点集合到自身的部分函数，其中每个节点映射到其后继节点，并且每个节点最终都可以从起始节点到达。（最后一个节点没有后继节点）。反转链表就意味着要反转这个函数，因为沿着链接前进然后向后穿过它应该会让你回到起点。

如果链表不包含环，则这个部分函数是单射（一对一），这意味着没有两个节点映射到相同的后继节点。单射函数确实可以被反转，这就是为什么你可以反转一个常规链表。但是，如果链表包含一个环（而不仅仅是一个大环），则存在两个具有相同后继节点的节点，因此该函数不是单射函数，因此没有逆函数。因此，如果链表有一个环，你不能反转链表并期望得到另一个链表。

但是，如果将链表视为一个更一般的图形，其中每个节点可以具有任意数量的入边或出边，则逆函数确实存在。只是它不再是一个链表了。

- templatetypedef

---

非常好的分解和清晰的解释。非常感谢。 - Sam

@templatetypedef - "如果您将链表视为更一般的图形，其中每个节点可以具有任意数量的入站或出站边，则其逆存在。" 您能稍微详细解释一下吗？该图仍然可能存在循环，这意味着您指出的同一问题仍然存在，即图中存在“具有相同后继节点的两个节点”。那么该情况将如何处理？ - Travis J

如果您有一个包含循环的链表并且反转所有边缘，则某些单元格可能具有多个出边。如果您希望结果是一个链接列表，则这是一个问题，但是如果允许每个节点有多个出边，则完全没有问题。这有意义吗？ - templatetypedef

但是，'last'节点指向'first'节点的特定循环并没有这个问题，并且在仍然是链表的情况下可以被反转。（例如，在问题示例中，如果F指向A） - MattCochrane

@MattCochrane 很好的观点，已修复。 - templatetypedef

Answer 2

原始列表为AB CDEF CDEF CDEF ...。要将其反转，您需要一个生成无限次数的FEDC，然后跟随BA的链表，因此我会说，没有办法构建一个能够生成该序列的链表。

- Brad Mace

---

但是，考虑到列表的使用者永远无法到达最终的BA，对于某些目的，在FEDC上循环可能作为一种反转的方式。 - Tony Delroy