2023 8 -14链表OJ（下）

struct ListNode *detectCycle(struct ListNode *head) {
    //解法1：分析结论法 L = n*C - X;  
    struct ListNode* slow,*fast;
    slow = fast =head;//刚开始都是从头走
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        //带环
        if(fast == slow)//相遇
        {
            struct ListNode* meet = slow;//相遇点
            //一个从头走，一个从相遇点走，最后一定会在入口点相遇
            while(head != meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    //不带环
    return NULL;
}
struct ListNode *detectCycle(struct ListNode *head){
    struct ListNode* slow,*fast;
    slow = fast =head;//刚开始都是从头走
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)//相遇
        {
            //两个相交链表，返回其交点
            struct ListNode* meet = slow;
            struct ListNode* newhead = meet->next;
            meet->next = NULL;
            //这个地方不能free(meet),因为你接下来算长度还会经过meet
            int len1 = 1;
            int len2 = 1;
            struct ListNode* head1 = head;
            struct ListNode* head2 = newhead;
            while(head1->next)
            {
                head1 = head1->next;
                len1++;
            }
            while(head2->next)
            {
                head2 = head2->next;
                len2++;
            }
            //找出长链表
            struct ListNode* longlist = head,*shortlist =newhead;
            if(len1 < len2)
            {
                longlist = newhead;
                shortlist = head;
            }
            int gap = abs(len1 - len2);
            //让长的先走gap步
            while(gap--)
            {
                longlist = longlist->next;
            }
            while(longlist != shortlist)
            {
                longlist = longlist->next;
                shortlist = shortlist->next;
            }
            return longlist;
        }
    }
    return NULL;
}

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
struct Node* copyRandomList(struct Node* head) {
    //1.拷贝
    struct Node* cur = head;
    while(cur)
    {
        struct Node* next = cur->next;
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        //赋值
        copy->val = cur->val;
        copy->next = next;
        cur->next = copy;
        //向后走
        cur = next;
    }
    cur = head;//从头来
    //2.置 copy random
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if(cur->random == NULL)
        {
            copy->random = NULL;
        }
        else
        {
            copy->random = cur->random->next;
        }
        //向后移动
        cur = next;
    }
    //3.解离
    struct Node* copyhead = NULL;
    struct Node* copytail = NULL;
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        if(copytail == NULL)//注意刚开始为空
        {
            copyhead = copytail = copy;
        }
        else
        {
            copytail->next = copy;
            copytail = copytail->next;
        }
        //恢复原链表
        cur->next = next;
        //向后走
        cur = next;
    }
    return copyhead;
}