链表经典面试题--链表修至圆满

1.环形链表

a.为什么一定会相遇，有没有可能会错过，永远追不上？请证明

b.slow一次走1步，fast走3步 4步 5步 n步还一定追得上吗请证明

2.环形链表2

3.随机链表的复制

1.环形链表

141. 环形链表 - 力扣（LeetCode）

思路：

快慢指针，慢指针走一步，快指针走两步

进环以后快指针开始追击慢指针

当快指针能追上慢指针就证明链表带环

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

面试问题：

a.为什么一定会相遇，有没有可能会错过，永远追不上？请证明

假设slow进环时，fast跟slow距离时N，fast追击slow的过程中距离变化如下：

N

N-1

N-2

...

2

1

0

每追击一次，距离缩小1，距离为0就是追上了

b.slow一次走1步，fast走3步 4步 5步 n步还一定追得上吗请证明

假设slow进环时，fast跟slow距离时N，

fast追击slow得过程只距离变化如下：

偶数奇数

N N

N-2 N-2

N-4 N-4

... ....

4 3

2 1

0 -1

追上了错过了---->进行新得一轮追击，距离变成C-1（假设C是环得长度）

两种情况：1.C-1是偶数 2.C-1是奇数

总结：

1.N是偶数，第一轮就追上了

2.N是奇数，第一轮追击会错过，距离变成C-1

a、如果C-1是偶数下一轮就追上了

b、如果C-1是奇数，那么就永远追不上

结论：如果同时存在N是奇数且C是偶数，那么就永远追不上

那么，N是奇数且C是偶数的情况是否一定存在呢？

假设slow进环时，fast跟slow距离时N，

slow走的距离是：L

slow进环时，假设fast已经在环里面转了x圈

fast走的距离 : L + x * C + C - N

假设fast走的距离是slow的3倍

3*L = L + x*C + C - N

||

2*L = (x+1)*C + C + N

||

偶数=（x+1）*偶数 - 奇数

由此，N是1奇数时，C也是奇数；N是偶数是，C也是偶数

只有奇数-奇数才能等于偶数

（x+1）*偶数一定等于偶数

所以，N是奇数且C是偶数不能同时存在，永远追不上的条件不成立

结论：一定能追上

N是偶数第一轮就追上了

N是奇数第一轮追不上，C-1是偶数第二轮就追上了

2.环形链表2

142. 环形链表 II - 力扣（LeetCode）

与上面一样

相遇时：slow走的路程：L+N; fast走的路程：L+x*C + N

假设fast走的路程时slow2倍

2*(L+N) = L+x*C + N

||

L+N=x*C

||

L=x*C-N

||

L=(x-1)C + C - N

由此，slow走到开始入环的第一个节点时恰好是head走到开始入环的第一个节点处

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

3.随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

思路：

把每个拷贝节点连接到原节点的后面

控制random

把拷贝节点拿下来尾插成新链表，恢复原链表

struct Node* copyRandomList(struct Node* head) {
	//把每个拷贝节点连接到原节点的后面
    struct Node* cur=head;
    while(cur)
    {
        struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
        copy->val=cur->val;
        copy->next=cur->next;
        cur->next=copy;

        cur=copy->next;
    }
    //控制random
    cur=head;
    while(cur)
    {
        struct Node* copy = cur->next;//拷贝节点已经连接到原节点的后面
        if(cur->random==NULL)
        {
            copy->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;//复制链表random指向原链表random指向的节点的拷贝节点
            //copy->random=cur->random;//错误，不能指向原链表的节点
        }
        cur=copy->next;//继续往下遍历
    }
    //把拷贝节点拿下来尾插成新链表，恢复原链表
    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;
}