当前位置：首页 > article >正文

链表带环问题（详解）

article 2025/3/1 3:33:31

在这里插入图片描述

🔆链表带环问题（详解）

🔆I 给定一个链表，判断链表中是否有环。
🔆II 给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回 NULL。
🔆复制带随机指针的链表
🔆结语

🔆I 给定一个链表，判断链表中是否有环。

OJ链接

解题思路：
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。
思路解释：

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

答案：

bool hasCycle(struct ListNode *head) {
    if(head == NULL || head->next == NULL)
        return false;
    struct ListNode* slow = head;
    struct ListNode* fast = head->next->next;
    while(slow != fast)
    {
        if(fast == NULL || fast->next == NULL)
            return false;
        slow = slow->next;
        fast = fast->next->next;
    }
    return true;
}

🔆II 给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回 NULL。

OJ链接

结论
让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
证明

答案：

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode *slow = head, *fast = head;
    while (fast != NULL) {
        slow = slow->next;
        if (fast->next == NULL) {
            return NULL;
        }
        fast = fast->next->next;
        if (fast == slow) {
            struct ListNode* ptr = head;
            while (ptr != slow) {
                ptr = ptr->next;
                slow = slow->next;
            }
            return ptr;
        }
    }
    return NULL;
}

🔆复制带随机指针的链表

OJ链接

链表实例：

1.根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面。

2.设置新链表的随机指针，第一个新节点的随机指针=第一个旧节点随机指针指向节点的下一个节点，依次类推。

3.解开旧链表与新链表的链接，恢复旧链表，链接新链表。

答案：

 struct Node* BuyNode(int x) {
     struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
     if (newnode == NULL){
         exit(-1);
     }
     newnode->val = x;
     newnode->next = NULL;
     return newnode;
 }

struct Node* copyRandomList(struct Node* head) {
	if (head == NULL) {
        return NULL;
    }

    //1、申请新节点，链接到每个旧节点的后面
    struct Node* cur = head, *next = NULL;
    while (cur) {
        struct Node* newnode = BuyNode(cur->val);
        next = cur->next;
        cur->next = newnode;
        newnode->next = next;
        cur = next;
    }

    //2、拷贝原链表的random指针，相对于新链表的相对位置
    cur = head;
    while (cur) {
        next = cur->next;
        if (cur->random == NULL) {
            next->random = NULL;
        }else {
            next->random = cur->random->next;
        }
        cur = next->next;
    }

    //3、解开新链表与旧链表的链接，恢复旧链表和新链表的链接
    cur = head;
    struct Node* newHead = cur->next;
    while (cur) {
        next = cur->next;
        cur->next = next->next;
        if (cur->next == NULL) {
            next->next = NULL;
        }else {
            next->next = cur->next->next;
        }
        cur = cur->next;
    }
    return newHead;
}