是否可以反转包含循环的链表？

Question

我正在看一些面试问题,其中一个问题是要反转一个包含循环的链表.所以假设我有一个如下链接列表:

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

然后反转列表将创建以下内容:

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

这里的问题是节点C应该指向哪个之间存在冲突.那么我们会消除C和F之间的联系吗？

Answer 1

在数学上,您可以将链接列表(可能包含循环)视为从一组节点到其自身的部分函数,​​其中每个节点映射到其后继节点,并且每个节点最终都可以从起始节点到达.(最后一个节点没有后继节点).反转链接列表然后需要反转这个功能,因为跟随一个链接然后向后移动它应该会让你回到你开始的地方.

如果链表不包含循环,则此部分函数是单射的(一对一),这意味着没有两个节点映射到同一个后继节点.内射函数确实可以反转,这就是为什么你可以反转常规链表.但是,如果列表包含一个循环,则有两个节点具有相同的后继节点,因此该函数不是单射的,因此不具有逆.所以不,如果列表有一个循环,你不能反转链表并期望获得另一个链表.

但是,如果将链接列表视为更一般的图形,其中每个节点可以具有任意数量的传入或传出边缘,则反向确实存在.它不再是链接列表了.