java代码怎样实现循环链表解决环形问题 java代码循环链表的应用实现技巧​

// 链表节点定义
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

// 循环链表或带有环的链表操作
class LinkedListCycleSolver {

    // 构建一个简单的循环链表（用于演示，实际应用可能更复杂）
    public Node createCircularList(int[] values) {
        if (values == null || values.length == 0) {
            return null;
        }
        Node head = new Node(values[0]);
        Node current = head;
        for (int i = 1; i < values.length; i++) {
            current.next = new Node(values[i]);
            current = current.next;
        }
        current.next = head; // 使链表循环
        return head;
    }

    // 检测链表中是否存在环
    public boolean hasCycle(Node head) {
        if (head == null || head.next == null) {
            return false;
        }
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;         // 慢指针每次走一步
            fast = fast.next.next;    // 快指针每次走两步

            if (slow == fast) {       // 如果相遇，则存在环
                return true;
            }
        }
        return false; // 快指针到达末尾或null，无环
    }

    // 如果存在环，找到环的入口节点
    public Node detectCycleStart(Node head) {
        if (head == null || head.next == null) {
            return null;
        }

        Node slow = head;
        Node fast = head;
        boolean cycleDetected = false;

        // 第一次相遇：检测环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                cycleDetected = true;
                break;
            }
        }

        if (!cycleDetected) {
            return null; // 无环
        }

        // 第二次相遇：找到环的入口
        slow = head; // 慢指针回到起点
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow; // 此时slow和fast相遇的节点就是环的入口
    }

    // 计算环的长度
    public int getCycleLength(Node head) {
        if (head == null || head.next == null) {
            return 0;
        }

        Node slow = head;
        Node fast = head;
        boolean cycleDetected = false;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                cycleDetected = true;
                break;
            }
        }

        if (!cycleDetected) {
            return 0; // 无环
        }

        // 环已检测到，从相遇点开始计数，直到再次回到相遇点
        int length = 0;
        Node current = slow.next; // 从相遇点的下一个节点开始
        while (current != slow) {
            length++;
            current = current.next;
        }
        return length + 1; // 加上自身
    }

    // 移除环（将环的末尾指向null）
    public void removeCycle(Node head) {
        Node cycleStart = detectCycleStart(head);
        if (cycleStart == null) {
            return; // 没有环，无需移除
        }

        Node ptr1 = head;
        Node ptr2 = cycleStart;

        // 找到环的入口节点的前一个节点
        // 这段逻辑在找到环入口后，需要找到连接到入口的那个节点
        // 另一种更直接的方式是：找到环入口后，让一个指针从入口开始走一圈，找到环的最后一个节点
        Node temp = cycleStart;
        while (temp.next != cycleStart) {
            temp = temp.next;
        }
        temp.next = null; // 将环的末尾指向null，打破循环
    }

    // 遍历循环链表（需要一个停止条件，比如遍历N次或回到起点）
    public void traverseCircularList(Node head, int maxSteps) {
        if (head == null) {
            System.out.println("链表为空。");
            return;
        }
        Node current = head;
        int count = 0;
        System.out.print("循环链表遍历: ");
        do {
            System.out.print(current.data + " ");
            current = current.next;
            count++;
            if (count >= maxSteps) { // 防止无限循环
                System.out.print("... (达到最大遍历步数)");
                break;
            }
        } while (current != head); // 遍历直到回到头节点
        System.out.println();
    }
}

null

next

null

null

null

null