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

目录

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;
}

感谢观看，再见