我正在看一些面试问题，其中一个要求反转包含循环的链表。所以假设我有一个如下所示的链接列表：
F <- E
| /\
V |
A -> B -> C -> D
然后反转列表将创建以下内容：
F -> E
/\ |
| V
A <- B <- C <- D
这里的问题是 C 应该指向的节点之间存在冲突。那么我们是否可以消除 C 和 F 之间的联系呢？
从数学上讲，您可以将链表（可能包含循环）视为从一组节点到其自身的部分函数，其中每个节点映射到其后继节点，并且每个节点最终都可以从起始节点到达。 （最后一个节点没有后继节点）。反转链接列表将需要反转此函数，因为跟随链接然后向后遍历它应该最终回到开始的地方。
如果链表不包含循环，则该部分函数是单射的（一对一），这意味着没有两个节点映射到相同的后继节点。单射函数确实可以反转，这就是为什么您可以反转常规链表。但是，如果列表包含一个循环（并且不仅仅是一个大循环），则有两个节点具有相同的后继，因此该函数不是单射的，因此没有逆函数。所以不，如果列表有循环，您不能反转链表并期望得到另一个链表。
但是，如果将链表视为更通用的图，其中每个节点可以具有任意数量的传入或传出边，则逆过程确实存在。它不再是一个链接列表了。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
