关于带环链表、深拷贝链表的记录

#include
#include
struct ListNode
{
    int val;
    struct ListNode* next;
};

struct ListNode2
{
    int val;
    struct ListNode2* next;
    struct ListNode2* random;
}

//判断一个链表是否带环

//1.为什么slow和fast一定会在环中相遇？会不会在环里面错过，永远遇不上？请证
//第一步：fast先进环，此时slow走了进环前一半的距离
//第二步：随着slow进环，fast已经在环里面走了一段，走了多少跟环的大小有关系
//          假设slow进环的时候，slow跟fast的距离是N，fast开始追slow
//          slow每次往前走一步，fast往前走两步，每追一次，判断一下相遇
//          每追一次，fast和slow的距离  减一
//          他们之间的距离最后减到0的时候，就是相遇的点
//
//2、为什么slow走一步，fast走两步，能不能fast走一次走3、4、5？请证明
  //  假设slow一次走一步，fast一次走三步
        //slow进环之后，fast跟slow距离为N

        //如果N是奇数，距离变成-1 ，意味着他们之间的距离变成C-1（C是环的长度）
        //如果C-1是奇数，那么就永远追不上
        //如果C-1是偶数，那么就可以追得上
//3、slow走1步，fast走2步，求环的入口点
//    结论：一个指针从相遇点开始走，一个指针从链表头开始走，他们会在环的入口点相遇
//    追上相遇的过程中 慢指针走的距离：L+X 
//                     快指针走的距离：L+N*C+X  (L是从头到入环点的距离，X是入还点到相遇点的距离，C是环的大小)
//                     快指针走的路程是慢指针的2倍
//                     2(L+X)=L+N*C+X
//                     L+L=N*C
//                     L=N*C-X
//
//    
//                   L=(N-1)*C+ C-X

//判断链表是否带环 ，并且找到入还点 
bool hasCycle(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if(fast == slow)
        {
            //相遇点
            struct ListNode* meet = slow;
            while(meet != head)
            {
                meet = meet->next;
                head = head->next;
            }
            return meet;//入环点
        }
    }
    return false;
}

//判断两个链表是否相交问题，如果相交返回相交的位置地址，如果不相交返回NULL
struct ListNode *getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    int num1 = 0;
    int num2 = 0;

    while(tailA->next)
    {
        num1++;
        tailA = tailA->next;
    }
    while(tailB->next)
    {
        num2++;
        tailB = tailB->next;
    }
    if(tailA == tailB)
    {
        //说明最后一个位置相同，两个链表相交
        int gab = abs(num1 - num2);
        if(num1 < num2)
        {
            longList = headB;
            shortList = headA;
        }
        while(gab--)
        {
            longList = longList->next;
        }
        while(longList != shortList)
        {
            longList = longList->next;
            shortList = shortList->next;
        }
        return longList;
    }
    else
    {
        return NULL;
    }
}

struct ListNode2* copyList(ListNode2* head)
{
    struct ListNode2* cur = head;
    struct ListNode2* copyHead = NULL, *copyTail = NULL;
    while(cur)
    {
        struct ListNode2* copy =  (struct ListNode2*)malloc(sizeof(struct ListNode2)) ;
        //插入节点
        copy->val = cur->val;
        copy->next = cur->next;
        cur->next = copy;
        cur = copy->next;
    }
        //把random复制到新创建的节点
    cur = head;
    while(cur)
    {
        struct ListNode2* copy = cur->next;
        if(cur->random = NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;

        cur = copy->next;
    }
    //把新创建的节点依次尾插到新的链表
    cur = head;
    while(cur)
    {
        struct ListNode2* copy = cur->next;
        struct ListNode2* next = copy->next;
        if(!copyTail)
            copyHead = copyTail = copy;
        else
        {
            copyTail->next = copy;
            copyTail = copy;
        }

        cur->next = next;
        cur = next;
        
    }
    //自己写的，只完成了复制链表
    
}