Simple Linked List: getting an ‘error – found cycle’ in code

I have this reverseList function:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

public ListNode reverseList(ListNode head) {
        ListNode dummyHead = new ListNode(0, head);
        ListNode prev = dummyHead;
        ListNode curr = dummyHead.next;
        ListNode future = curr.next;
        
        
        while (future != null) {
            curr.next = prev;
            prev = curr;
            curr = future;
            future = future.next;
        }
        
        curr.next = prev;
        dummyHead.next = curr;   
        
        return dummyHead.next;
    }

But I get an error that says ‘found cycle in the LinkedList’ when iterating specifically through ‘curr.next = prev’ and ‘prev = curr’. Any ideas on why this might be occuring?

Thanks

Answer

As far as I can tell you are testing your code with some kind of judge since there is no “found cycle” error in java. The error you are thinking of gave the name to this website, namely, StackOverflowError runtime error. This may occur when a linked list contains a cycle. Unfortunately, you can not reverse a linked list with cycles. For more details, check this post.

When it comes to your code, what your reverseList method does is that it first reverses a linked list then adds an extra node with a value zero to the end of it. This extra node points to the head of the list, thus creating a cycle. Here is the fixed version:

    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        ListNode future = null;

        while (curr != null) {
            future = curr.next;
            curr.next = prev;
            prev = curr;
            curr = future;
        }

        head = prev;
        return head;
    }