Remove Loop in Linked List Using Java

2025 年 5 月 5 日 | 阅读 6 分钟

链表中的环是指链表中的一个节点指向了链表中的一个较早的节点，从而形成了一个循环，而不是链表的末尾。检测并移除这个环可以恢复链表的线性结构，防止无限遍历，并提高其在后续操作中的可靠性。

方法：使用哈希

这种方法在遍历链表时使用 HashSet 来存储已访问的节点。如果一个节点被再次访问（已存在于 HashSet 中），则检测到环，并通过更新前一个节点的 next 指针为 null 来移除环。

算法

步骤 1： 创建一个空的 HashSet 来存储已访问的节点，并创建一个变量 previousNode 来跟踪前一个节点。

步骤 2： 从头节点开始，遍历链表，检查每个节点。

步骤 3： 对于每个节点，检查它是否已存在于 HashSet 中（表示存在环）。如果检测到环，通过设置 previousNode.next = null 来移除它。

步骤 4： 如果未检测到环，则将当前节点添加到 HashSet 中，并移动到下一个节点。

步骤 5： 继续此过程，直到到达链表的末尾（即 headNode 变为 null），确保如果存在环则将其移除。

实施

文件名：LinkedListLoopRemover.java

import java.util.HashSet;
class ListNode {
    int data; // Data field to store the value of the node
    ListNode next; // Pointer to the next node in the linked list
    // Constructor to initialize a node with a given value
    ListNode(int value) {
        data = value; // Assign the passed value to the data field
        next = null; // Initially, the next node is set to null
    }
}
// Define the LinkedListLoopRemover class, which contains the methods for loop detection and removal
public class LinkedListLoopRemover {
    // Method to print the nodes of the linked list from the start node
    static void printList(ListNode startNode) {
        // Traverse the linked list starting from the startNode
        while (startNode != null) {
            System.out.print(startNode.data + " "); // Print the data of the current node
            startNode = startNode.next; // Move to the next node
        }
    }
    // Method to detect and remove a loop in the linked list
    static void removeLoop(ListNode headNode) {
        HashSet<ListNode> visitedNodes = new HashSet<>(); // Create a HashSet to store the visited nodes
        ListNode previousNode = null; // Variable to keep track of the previous node during traversal
        // Traverse the linked list until we reach the end (null)
        while (headNode != null) {
            // Check if the current node has already been visited, which indicates a loop
            if (visitedNodes.contains(headNode)) {
                previousNode.next = null; // Remove the loop by setting the previous node's next pointer to null
                return; // Exit the method since the loop has been removed
            } else {
                visitedNodes.add(headNode); // Add the current node to the visited set
                previousNode = headNode; // Update the previous node to the current node
                headNode = headNode.next; // Move to the next node in the linked list
            }
        }
    }
    // Main method to create a linked list, introduce a loop, and test the loop removal
    public static void main(String[] args) {
        ListNode headNode = new ListNode(5); // Create the first node with value 5
        headNode.next = new ListNode(12); // Link the second node with value 12
        headNode.next.next = new ListNode(7); // Link the third node with value 7
        headNode.next.next.next = new ListNode(3); // Link the fourth node with value 3
        headNode.next.next.next.next = new ListNode(8); // Link the fifth node with value 8
        headNode.next.next.next.next.next = headNode.next;
        // Call the removeLoop method to detect and remove any loop in the list
        removeLoop(headNode);
        // Print the linked list after removing the loop to verify the result
        printList(headNode);
    }
}   

输出

 
5 12 7 3 8

时间复杂度： O(N) - 每个节点仅遍历一次。

辅助空间： O(N) - 使用 HashSet 存储已访问的节点。

方法：Floyd 循环检测算法

Floyd 循环检测算法，也称为龟兔赛跑方法，使用两个以不同速度移动的指针来检测链表中的环。如果存在循环，两个指针将在循环内部相遇，从而能够以恒定的空间复杂度有效地检测和移除环。

算法

步骤 1： 将两个指针 slowPointer 和 fastPointer 设置在链表的头部。

步骤 2： 将 slowPointer 向前移动一步，将 fastPointer 向前移动两步。如果它们相遇，则检测到环。

步骤 3： 将 slowPointer 重置到头部。一次一步地移动 slowPointer 和 fastPointer，直到它们在循环的起点相遇。

步骤 4： 一旦找到循环的起点，就将最后一个节点的 nextNode 指针设置为 null，以打破循环。

步骤 5： 从头部打印链表，以确认环已被移除。

实施

文件名：LinkedListLoopRemover.java

// Define the ListNode class to represent a node in the linked list
class ListNode {
    int value; // Variable to store the value of the node
    ListNode nextNode; // Pointer to the next node in the linked list
    // Constructor to initialize a new node with a given value
    ListNode(int val) {
        value = val; // Assign the value to the node
        nextNode = null; // Initialize the next pointer to null (no next node initially)
    }
}
// Define the LinkedListLoopRemover class, which contains the methods for loop detection and removal
public class LinkedListLoopRemover {
    // Method to detect and remove a loop in the linked list
    static void detectAndRemoveCycle(ListNode headNode) {
        if (headNode == null || headNode.nextNode == null)
            return; // Exit the method as there's no loop to remove
        ListNode slowPointer = headNode, fastPointer = headNode; // Initialize two pointers (slow and fast)
        // Move the slow pointer one step at a time and the fast pointer two steps at a time
        slowPointer = slowPointer.nextNode;
        fastPointer = fastPointer.nextNode.nextNode;
        // Use the slow and fast pointers to detect if there is a loop in the list
        while (fastPointer != null && fastPointer.nextNode != null) {
            if (slowPointer == fastPointer) // If slow and fast pointers meet, a loop is detected
                break; // Exit the loop as we've detected a cycle
            slowPointer = slowPointer.nextNode; // Move the slow pointer one step forward
            fastPointer = fastPointer.nextNode.nextNode; // Move the fast pointer two steps forward
        }
        // If a loop is detected, slowPointer and fastPointer will meet at some point
        if (slowPointer == fastPointer) {
            slowPointer = headNode; // Reset the slow pointer to the head node of the list
            if (slowPointer != fastPointer) {
                // If the slow and fast pointers are not at the same node, move them one step at a time
                // until they meet at the node where the loop starts
                while (slowPointer.nextNode != fastPointer.nextNode) {
                    slowPointer = slowPointer.nextNode; // Move slow pointer one step forward
                    fastPointer = fastPointer.nextNode; // Move fast pointer one step forward
                }
                fastPointer.nextNode = null; // Remove the loop by setting the next pointer of the last node in the loop to null
            } else {
                // If the loop is at the start node, keep moving the fast pointer until it reaches the last node of the loop
                while(fastPointer.nextNode != slowPointer) {
                    fastPointer = fastPointer.nextNode; // Move fast pointer one step forward
                }
                fastPointer.nextNode = null; // Remove the loop by setting the next pointer of the last node to null
            }
        }
    }
    // Method to print the linked list from the start node
    static void printList(ListNode currentNode) {
        // Traverse the linked list and print each node's value
        while (currentNode != null) {
            System.out.print(currentNode.value + " "); // Print the current node's value
            currentNode = currentNode.nextNode; // Move to the next node in the list
        }
    }
    // Main method to test the loop removal functionality
    public static void main(String[] args) {
        ListNode headNode = new ListNode(100);
        headNode.nextNode = new ListNode(200);
        headNode.nextNode.nextNode = new ListNode(300);
        headNode.nextNode.nextNode.nextNode = new ListNode(400);
        headNode.nextNode.nextNode.nextNode.nextNode = new ListNode(500);
        headNode.nextNode.nextNode.nextNode.nextNode.nextNode = headNode.nextNode.nextNode;
        // Call the detectAndRemoveCycle method to detect and remove any loop in the list
        detectAndRemoveCycle(headNode);
        // Print the linked list after removing the loop to verify the result
        printList(headNode); // This will print the list without the loop
    }
}   

输出

 
100 200 300 400 500

时间复杂度：O(n)

辅助空间复杂度: O(1)

下一主题Java 中的 Keith 数

← 上一个下一个 →

Remove Loop in Linked List Using Java

方法：使用哈希

算法

实施

方法：Floyd 循环检测算法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Remove Loop in Linked List Using Java

方法：使用哈希

算法

实施

方法：Floyd 循环检测算法

算法

实施

相关帖子

Java 中的 Tribonacci 级数

Java Testing Tools

Java TreeMap 按值排序

FieldPosition getEndIndex() method in Java with Example

Java 程序生成随机十六进制字节

Java 程序在不使用 / 和 % 运算符的情况下检查数字是否为 5 的倍数

Unique Number in Java Program

Java 中不能被子类化的类是哪个

DoubleBuffer mark() methods in Java with Examples

Java Heap

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器