简单链表：在代码中得到一个 'error - found cycle'

Question

我有这个 reverseList 函数：


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

但是当我专门遍历 'curr.next = prev' 和 'prev = curr' 时，我得到一个错误提示 'found cycle in the LinkedList'。关于为什么会发生这种情况的任何想法？

谢谢

Answer 1

据我所知，您正在使用某种判断来测试您的代码，因为 java 中没有“发现循环”错误。您所想到的错误为该网站命名，即 WhosebugError 运行时错误。当链表包含循环时，可能会发生这种情况。不幸的是，您不能反转带循环的链表。有关详细信息，请查看此 post.

当涉及到您的代码时，您的 reverseList 方法所做的是它首先反转链表，然后在其末尾添加一个值为零的额外节点。这个额外的节点指向列表的头部，从而创建一个循环。这是固定版本：

    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;
    }

简单链表：在代码中得到一个 'error - found cycle'

Simple Linked List: getting an 'error - found cycle' in code

java

linked-list

data-structures