简单链表：获取代码中的'error - found cycle'

Question

我有这个reversellist函数:

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

但我得到一个错误，说'发现周期在LinkedList'当迭代通过' current '。Next = prev'和'prev = curr'。你知道为什么会这样吗?

感谢

Answer 1

据我所知，你是在用某种判断器测试你的代码，因为没有"发现循环"。java错误。您正在考虑的错误给这个网站的名称，即StackOverflowError运行时错误。当链表包含一个循环时，可能会发生这种情况。不幸的是，你不能用循环来反转链表。更多详细信息，请查看这篇文章。

当涉及到你的代码时，你的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;
}