深入了解环形链表

一、基础知识

环形链表是一种特殊的链表，和普通链表不同的地方在于，最后一个节点的下一个节点指针不是指向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 < nums.size(); ++i) {
        ListNode* cur = new ListNode(nums[i]);
        pre->next = cur;
        pre = cur;
    }
    pre->next = head; //最后一个节点指向第一个节点
    return head;
}

  

三、遍历环形链表

遍历环形链表需要使用一种新的方式，因为环形链表没有结束节点。一般来说，我们可以使用while循环来遍历链表，也可以使用do while循环来保证至少执行一次循环。

具体实现时，我们可以使用一个指针来遍历链表，从第一个节点开始，遍历到最后一个节点。由于最后一个节点的指针指向第一个节点，因此可以使用指针是否等于头节点来判断是否已经遍历了整个链表。

void traverseCycleList(ListNode* head) {
    if (!head) return;
    ListNode* cur = head;
    do {
        cout << cur->val << " ";
        cur = cur->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 < head->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;
}