使用reverseList解决链表循环问题

Question

我最近尝试解决 LeetCode 问题 141，“链表循环”，#问题的链接，我找到了一个可行的解决方案，但让我感到困惑。我希望能澄清这个特定解决方案的工作原理。

解释：

我最初考虑通过反转链表来解决问题，这看起来很有希望。然而，仔细检查代码后，我很困惑如果没有循环，

head->next

怎么会是NULL。反转后不应该指向第二个节点吗？

这是我的代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
   bool hasCycle(ListNode *head)
    {
        if(head){
        reverseList(head);
        if (head->next != NULL)
        {
            return true;
        }
        }
        return false;
    }
    void reverseList(ListNode *head)
    {
        ListNode *temp = head;
        ListNode *next = head->next;
        head->next = NULL;
        while (temp != NULL)
        {
            temp = next;
            if (next != NULL)
            {
                next = temp->next;
                temp->next = head;
                head = temp;
            }
        }
    }
};

我知道其他解决方案，但我只是尝试所有可能的解决方案

Answer 1

反转方法是检测是否存在循环的巧妙技巧。有两种情况需要分析：

输入列表无循环

关于你写的这个场景：

我很困惑如果没有循环，

head->next

怎么可能是

NULL

。

在

reverseList

中，这是通过赋值显式完成的：

head->next = NULL

并且由于在反转算法期间不会再次访问该节点，因此这是最终的。

反转后不应该指向第二个节点吗？

也许混淆来自这样的假设：反转后，变量

head

将引用reversed列表的第一个节点，但这不是真的。

head

的

hasCycle

变量永远不会更新，因此它一直引用 是 列表的第一个节点，但在反转完成后 成为 的尾部节点。

例如，如果输入列表是：

      head  
       ↓
       1 → 2 → 3 → 4 → null

...那么逆转就会成功：

      head  
       ↓
null ← 1 ← 2 ← 3 ← 4

对节点 4 的引用由

reverseList

的主调用返回，因为它是现在反转列表的新头。但此返回的引用将被忽略，因为该算法不需要它。相反，我们用

head

维护对发生任何反转之前的头节点的引用。

输入列表有循环

这是您没有询问的场景，但在我看来，这是更有趣的描述案例。

我们以这个列表为例：

      head  
       ↓
       1 → 2 → 3 → 4
           ↑       │
           └───────┘

现在反转将像往常一样进行，并且在某个时刻该过程将到达反向引用：

      head   head' temp
       ↓       ↓   ↓
null ← 1 ← 2 ← 3   4
           ↑       │
           └───────┘
           ↑
         next
         

这是执行

temp->next = head

之前的状态。 （我为

head'

添加了撇号，以表明它是

reverseList

中的局部变量，而

head

仍然是

hasCycle

中的变量）

所以现在列表中已经颠倒的部分会被再次访问，方向相反：

      head        head' 
       ↓           ↓
null ← 1 ← 2 ← 3 ← 4


       ↑   ↑  
     next temp

更进一步：

      head         
       ↓
null ← 1   2 ← 3 ← 4
           │       ↑
           └───────┘
 ↑     ↑   ↑  
next temp head'

...最后一步：

      head         
       ↓
null   1 → 2 ← 3 ← 4
           │       ↑
           └───────┘
 ↑     ↑  
temp head'

在这里我们看到

head->next

 再次指向原始顺序中的第二个节点。这是

hasCycle

可以检测到的效果。一般来说，在有循环的列表上调用 

reverseList

 会导致循环反转，但不参与该循环的节点将恢复其原始链接。生成的列表将不包含具有 

next

 引用（即 

NULL

）的节点。

我希望这能澄清这一点。