java的單鏈表環操作有哪些

# Java的單鏈表環操作有哪些

## 目錄
1. [單鏈表與環的基本概念](#單鏈表與環的基本概念)
2. [檢測單鏈表是否存在環](#檢測單鏈表是否存在環)
   - [哈希表法](#哈希表法)
   - [快慢指針法](#快慢指針法)
3. [計算環的長度](#計算環的長度)
4. [尋找環的入口節點](#尋找環的入口節點)
5. [斷開鏈表中的環](#斷開鏈表中的環)
6. [完整代碼示例](#完整代碼示例)
7. [應用場景與總結](#應用場景與總結)

---

## 單鏈表與環的基本概念
單鏈表是由節點組成的線性數據結構，每個節點包含：
- **數據域**：存儲實際數據
- **指針域**：指向下一個節點的引用

```java
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

鏈表環指鏈表中某個節點的next指針指向了鏈表中它前面的某個節點，形成閉環。

檢測單鏈表是否存在環

哈希表法

時間復雜度：O(n)
空間復雜度：O(n)

public boolean hasCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    while (head != null) {
        if (visited.contains(head)) {
            return true;
        }
        visited.add(head);
        head = head.next;
    }
    return false;
}

快慢指針法

時間復雜度：O(n)
空間復雜度：O(1)

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    
    ListNode slow = head;
    ListNode fast = head.next;
    
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

計算環的長度

1. 先使用快慢指針找到相遇點
2. 從相遇點開始計數，直到再次回到該點

public int cycleLength(ListNode head) {
    ListNode meetNode = detectMeetingNode(head);
    if (meetNode == null) return 0;
    
    int length = 1;
    ListNode current = meetNode.next;
    while (current != meetNode) {
        length++;
        current = current.next;
    }
    return length;
}

private ListNode detectMeetingNode(ListNode head) {
    // 快慢指針實現...
}

尋找環的入口節點

數學推導：
設鏈表頭到入口距離為a，入口到相遇點距離為b，環長為L
根據快慢指針速度關系可得：2(a+b) = a + b + kL ? a = (k-1)L + (L-b)

public ListNode detectCycleStart(ListNode head) {
    ListNode meetNode = detectMeetingNode(head);
    if (meetNode == null) return null;
    
    ListNode ptr1 = head;
    ListNode ptr2 = meetNode;
    
    while (ptr1 != ptr2) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
    }
    return ptr1;
}

斷開鏈表中的環

找到入口節點后，將其前驅節點的next置為null

public void breakCycle(ListNode head) {
    ListNode cycleStart = detectCycleStart(head);
    if (cycleStart == null) return;
    
    ListNode current = cycleStart;
    while (current.next != cycleStart) {
        current = current.next;
    }
    current.next = null;
}

完整代碼示例

public class LinkedListCycleOperations {
    
    // 節點定義
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    
    // 檢測環
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }
    
    // 找環入口
    public ListNode detectCycleStart(ListNode head) {
        ListNode meetNode = getMeetingNode(head);
        if (meetNode == null) return null;
        
        ListNode ptr1 = head, ptr2 = meetNode;
        while (ptr1 != ptr2) {
            ptr1 = ptr1.next;
            ptr2 = ptr2.next;
        }
        return ptr1;
    }
    
    private ListNode getMeetingNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return slow;
        }
        return null;
    }
    
    // 計算環長
    public int getCycleLength(ListNode head) {
        ListNode meetNode = getMeetingNode(head);
        if (meetNode == null) return 0;
        
        int length = 1;
        ListNode current = meetNode.next;
        while (current != meetNode) {
            length++;
            current = current.next;
        }
        return length;
    }
    
    // 斷環
    public void breakCycle(ListNode head) {
        ListNode cycleStart = detectCycleStart(head);
        if (cycleStart == null) return;
        
        ListNode prev = cycleStart;
        while (prev.next != cycleStart) {
            prev = prev.next;
        }
        prev.next = null;
    }
}

應用場景與總結

典型應用場景

1. 內存管理中的循環引用檢測
2. 網絡路由檢測環路
3. 并發編程中的死鎖檢測

性能對比

總結

1. 快慢指針法是解決鏈表環問題的黃金標準
2. 理解數學原理比記憶代碼更重要
3. 實際開發中需根據場景選擇合適方法

擴展思考：如何將這些方法應用于雙向鏈表的環檢測？ “`

注：實際使用時需要： 1. 替換示意圖URL為真實圖片 2. 根據具體需求調整代碼細節 3. 補充更多實際案例和性能測試數據 4. 擴展部分可增加多語言實現對比