面试高频~单链表OJ题总结(二)

文章目录

1.力扣141:环形链表

给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。
面试高频~单链表OJ题总结(二)
分析:
1.让快指针一次走两步,慢指针一次走一步,如果相遇即有环
2.快指针走到NULL说明无环

bool hasCycle(struct ListNode *head) {
    struct ListNode* fist=head;
    struct ListNode* slow=head;
    while(fist&&fist->next){
        fist=fist->next->next;//快指针一次走两步
        slow=slow->next;//慢指针一次走一步
        if(fist==slow){
            return true;//相遇说明有环
        }
    }
    //快指针走到NULL说明链表无环
    return false;
}

思考:
1.为什么快指针一次走两步慢指针一次走一步可以?
答:假设链表带环,两个指针最后都会进入环,快指针先进环,慢指针后进环。最差情况下两个指针之间的距离刚好就是环的长度。此时,两个指针每移动一次,之间的距离就缩小一步,不会出现每次刚好是套圈的情况,因此:在 慢指针走到一圈之前,快指针肯定是可以追上慢指针的,即相遇。
2.快指针一次走三步/四步,慢指针一次走一步可不可以?
答:不可以。
例:
面试高频~单链表OJ题总结(二)

2.力扣142:环形链表找入口

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。 如果链表中有某个节点,可以通过连续跟踪 next指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。 不允许修改 链表。

分析:
1.先判断是否是有环的 (即第一题解题法)

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

面试高频~单链表OJ题总结(二)
2.在判断是否为环时快慢指针走的路径 快指针=L+nR+X 慢指针=L+X
注意:
(1).慢指针进环时,快指针已经绕环n圈 n>=1;因为快指针至少经过一次相遇点,再与慢指针相遇
(2).慢指针入环后,快慢指针一定会在一圈内相遇
快指针的速度又是慢指针2倍:即 2*(L+X)=L+X+nR
即L=nR-x(n的大小取决于环的大小和起点到相遇点的距离)
结论:一个指针从链表起始位置走,一个指针从相遇点开始走,每次走一步,两指针会在入口点相遇

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *fist=head,*slow=head;
    if(head==NULL||head->next==NULL){
        return NULL;
    }
    while(fist&&fist->next){
        fist=fist->next->next;
        slow=slow->next;
        //如果相遇,让快指针回到起点
        if(fist==slow){
            slow=head;
            //再次相遇,相遇点就是入口点
            while(slow!=fist){
                slow=slow->next;
                fist=fist->next;
            }
            return slow;
            break;
        }
    } 
    return NULL;
}

3.力扣160:相交链表

给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
图示两个链表在节点 c1 开始相交 题目数据 保证 整个链式结构中不存在环。 注意,函数返回结果后,链表必须 保持其原始结构。
图示两个链表在节点 c1 开始相交:
面试高频~单链表OJ题总结(二)

分析:
何为相交:

1.用双指针解决 pA遍历headA一遍传到headB,pB遍历headB一遍传到headA,两指针会在相交点相遇
面试高频~单链表OJ题总结(二)
2.如果是两个不相交链表,pA和pB会同时遍历完headA和headB,到达NULL

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* pA=headA;
    struct ListNode* pB=headB;
    if(headA==NULL||headB==NULL){
        return NULL;
    }
    while(pA!=pB){
        if(pA==NULL){
            pA=headB;
        }
        else{
            pA=pA->next;
        }
        if(pB==NULL){
            pB=headA;
        }
        else{
            pB=pB->next;
        }
        }
        return pA;
}

4.力扣138:复制带随机指针的链表

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点。构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ,同样有
x.random --> y 。

返回复制链表的头节点。

面试高频~单链表OJ题总结(二)
分析:
1.第一步:复制原链表的val域,插入到原结点的后面
2.第二步:复制原链表的random域
3.分割链表,还原原链表

面试高频~单链表OJ题总结(二)

struct Node* copyRandomList(struct Node* head) {
    struct Node* cur=head;
    //1.复制原结点的val域原结点的后面
    while(cur){
        struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
        newnode->val=cur->val;

        newnode->next=cur->next;
        cur->next=newnode;
        cur=newnode->next;
    }
    //2.复制结点的random域
    cur=head;
    while(cur){
        struct Node* prev=cur->next;
        if(cur->random==NULL){
        prev->random=NULL;
        }
        else{
        prev->random=cur->random->next;
        }
        cur=prev->next;
    }
     //3.断开链表 
    struct Node* newhead=NULL;
    struct Node* tail=NULL;
    cur=head;
    while(cur){
        struct Node* copy=cur->next;
        struct Node* next=copy->next;
        if(tail==NULL){
            newhead=tail=copy;
        } 
        else{
            tail->next=copy;
            tail=copy;
        }
        cur->next=next;
        cur=next;
    }
    return newhead;
}
上一篇:菜学C++ Day56 OJ题目1190 对角线I


下一篇:ip判断(oj)