深入了解環形鏈表

一、基礎知識

環形鏈表是一種特殊的鏈表，和普通鏈表不同的地方在於，最後一個節點的下一個節點指針不是指向NULL，而是指向鏈表的第一個節點。這樣就形成了一個環，因此也稱為循環鏈表。在實際開發中，環形鏈表可以用於解決某些循環問題。

定義環形鏈表時，我們需要定義一個節點結構體，其中至少包含兩個屬性：節點的值和下一個指針。同時，由於環形鏈表最後一個節點指向第一個節點，因此需要在定義節點結構體中加一個額外的指針屬性，表示最後一個節點指向第一個節點。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

二、創建環形鏈表

創建一個環形鏈表需要注意的是，在最後一個節點的指針指向第一個節點時，需要先判斷是否為NULL指針，如果是NULL指針，則將該指針指向第一個節點。

ListNode* createCycleList(vector& nums) {
    if (nums.empty()) return NULL;
    ListNode* head = new ListNode(nums[0]);
    ListNode* pre = head;
    for (int i = 1; i next = cur;
        pre = cur;
    }
    pre->next = head; //最後一個節點指向第一個節點
    return head;
}

三、遍歷環形鏈表

遍歷環形鏈表需要使用一種新的方式，因為環形鏈表沒有結束節點。一般來說，我們可以使用while循環來遍歷鏈表，也可以使用do while循環來保證至少執行一次循環。

具體實現時，我們可以使用一個指針來遍歷鏈表，從第一個節點開始，遍歷到最後一個節點。由於最後一個節點的指針指向第一個節點，因此可以使用指針是否等於頭節點來判斷是否已經遍歷了整個鏈表。

void traverseCycleList(ListNode* head) {
    if (!head) return;
    ListNode* cur = head;
    do {
        cout <val <next;
    } while (cur != head);
    cout << endl;
}

四、插入節點

對於環形鏈表，插入節點的一般操作與普通鏈表一致，只需要注意插入位置的前繼節點和後繼節點即可。

ListNode* insertCycleNode(ListNode* head, int value) {
    ListNode* node = new ListNode(value);
    if (!head) {
        node->next = node;
        return node;
    }
    ListNode* cur = head;
    while (cur->next != head) {
        if (cur->next->val >= value) {
            break;
        }
        cur = cur->next;
    }
    node->next = cur->next;
    cur->next = node;
    if (node->val val) {
        head = node;
    }
    return head;
}

五、刪除節點

刪除環形鏈表中的節點操作也和普通鏈表類似，需要注意的是刪除的節點如果是最後一個節點，需要額外操作將最後一個節點的指針指向新的最後一個節點。

ListNode* deleteCycleNode(ListNode* head, int value) {
    if (!head) return NULL;
    ListNode* pre = head, *cur = head->next;
    while (cur != head) {
        if (cur->val == value) {
            pre->next = cur->next;
            if (cur == head) {
                head = pre->next;
            }
            delete cur;
            return head;
        }
        pre = cur;
        cur = cur->next;
    }
    if (head->val == value) { //刪除的是頭結點
        pre->next = head->next;
        delete head;
        head = pre->next;
    }
    return head;
}