Linked List Cycle problem solving using reverseList

Question

I recently attempted to solve LeetCode problem 141, Linked List Cycle:

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. [...]

Return true if there is a cycle in the linked list. Otherwise, return false.

I found a solution that reverses the linked list. This seemed a promising idea.

Question

I'd appreciate some clarification on how this particular solution functions. I'm puzzled by how head->next could be NULL if there's no cycle. Shouldn't it point to the second node after reversing?

Here is the code:

/**
 * 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

The reversal approach is a neat trick to detect whether there is a cycle or not. There are two cases to analyse:

The input list has no cycle

About this scenario you wrote:

I'm puzzled by how head->next could be NULL if there's no cycle.

In reverseList, this is explicitly done with the assignment: head->next = NULL and as that node is not visited again during the reversal algorithm, this is final.

Shouldn't it point to the second node after reversing?

Maybe the confusion comes from an assumption that after the reversal, the variable head will reference the first node of the reversed list, but this is not true. The head variable of hasCycle is never updated, so it keeps referencing the same node that was the first node of the list, but has become the tail after the reversal has completed.

For example, if the input list is:

      head  
       ↓
       1 → 2 → 3 → 4 → null

... then the reversal will make it:

      head  
       ↓
null ← 1 ← 2 ← 3 ← 4

The reference to node 4 is returned by the main call of reverseList, as it is the new head of the now reversed list. But this returned reference is ignored because it is not needed for this algorithm. Instead, we maintain with head a reference to the node that was the head before any reversal occurred.

The input list has a cycle

This is the scenario you didn't ask about, but in my opinion it is the more interesting case to describe.

Let's take as example this list:

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

Now the reversal will proceed like usual and at some point that process will reach the backreference:

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

This is the state just before temp->next = head is executed. (I added an apostrophe for head' so to indicate it is the local variable in reverseList, while head is still the variable in hasCycle)

So now the part of the list that was already reversed, is visited again, in opposite direction:

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


       ↑   ↑  
     next temp

And one step further:

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

...and the last step:

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

And here we see that head->next points again to what was the second node in the original order. This is an effect that hasCycle can detect. In general, calling reverseList on a list that has a cycle, will result in the cycle to be reversed, but the nodes that do not participate in that cycle will have their original links restored. The resulting list will have no node with a next reference that is NULL.

I hope this clarifies it.