时间戳

首页 > 解决方案 > 简单链表：在代码中获取“错误 - 发现循环”

java - 简单链表：在代码中获取“错误 - 发现循环”

问题描述

我有这个 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'进行迭代时，我得到一个错误，说'在LinkedList中找到循环'。关于为什么会发生这种情况的任何想法？

谢谢

标签： javadata-structureslinked-list

解决方案

据我所知，您正在使用某种判断来测试您的代码，因为 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;
    }

推荐阅读