是否可以反转包含循环的链表？
我正在看一些面试问题，其中一个要求反转包含循环的链表。因此，假设我有一个如下所示的链接列表：
F <- E
| /\
V |
A -> B -> C -> D
然后反转该列表将创建以下内容：
F -> E
/\ |
| V
A <- B <- C <- D
这里的问题是 C 应该指向的节点之间存在冲突。那么我们是否可以消除 C 和 F 之间的联系呢？
I'm looking at some interview questions, and one of them asks to reverse a linked list that contains a cycle. So suppose I had a linked list like the following:
F <- E
| /\
V |
A -> B -> C -> D
Then reversing the list would create the following:
F -> E
/\ |
| V
A <- B <- C <- D
The problem here is that there's a conflict between which nodes C should be pointing at. So would we just eliminate the link between C and F?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
从数学上讲，您可以将链表（可能包含循环）视为从一组节点到其自身的部分函数，其中每个节点映射到其后继节点，并且每个节点最终都可以从起始节点到达。 （最后一个节点没有后继节点）。反转链表就需要反转这个函数，因为跟随一个链接然后向后遍历它应该会让你回到开始的地方。
如果链表不包含循环，则该部分函数是单射的（一对一），这意味着没有两个节点映射到相同的后继节点。单射函数确实可以反转，这就是为什么你可以反转常规链表。但是，如果列表包含一个循环（并且不仅仅是一个大循环），则有两个节点具有相同的后继，因此该函数不是单射的，因此没有逆函数。所以不，如果列表有循环，您不能反转链表并期望得到另一个链表。
但是，如果将链表视为更通用的图，其中每个节点可以具有任意数量的传入或传出边，则逆过程确实存在。它不再是一个链接列表了。
Mathematically, you can think of a linked list (possibly containing a cycle) as a partial function from a set of nodes into itself, where each node maps to its successor and every node is eventually reachable from the start node. (The last node has no successor). Reversing a linked list would then entail inverting this function, since following a link and then going backwards across it should end you up back where you started.
If the linked list does not contain a cycle, then this partial function is injective (one-to-one), meaning that no two nodes map to the same successor. Injective functions can indeed be inverted, which is why you can reverse a regular linked list. However, if the list contains a cycle (and isn’t just one large cycle), then there are two nodes with the same successor, so the function is not injective and thus does not have an inverse. So no, you cannot reverse the linked list and expect to get another linked list, if the list has a cycle.
However, if you treat the linked list as a more general graph in which each node can have any number of incoming or outgoing edges, then the inverse does exist. It's just not a linked list anymore.
原始列表将是 AB CDEF CDEF CDEF ... 要反转，您需要一个无限次生成
FEDC的链表，后跟BA，所以我想说不，没有办法构建一个可以生成该序列的链表。The original list would be
AB CDEF CDEF CDEF ...To reverse that you'd need a linked list that generatesFEDCan infinite number of times followed byBA, so I'd say no, there's no way to build a linked list that would generate that sequence.