• leetcode数据结构与算法刷题（三）

    目录

    第一题 交叉链表

    思想：

    注意点 

    第一步先求两个链表的长度

    第二步 让长的先走，当长短一样时一起走。

    犯错点

     第二题 判断是有环

     思想：

     注意

    错误分享

    第三题（重点面试题）

     思路：

     这题面试问题🧐😎🤓🫠⭐

     第一题 为什么他们会在入口出相遇

    第二题 L = N*C -X 怎么得来的

    第三题 slow一次走一步，fast一次走2步一定会相遇吗

    第四题 slow一次走1步，fast一次走三步会相遇吗

    第五题 slow一次走n步，fast一次走m步可以追上吗

    第一题 交叉链表

    简单
    相关标签
    相关企业

    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

    图示两个链表在节点 c1 开始相交：

    题目数据 保证 整个链式结构中不存在环。

    注意，函数返回结果后，链表必须 保持其原始结构 。

    自定义评测：

    评测系统 的输入如下（你设计的程序 不适用 此输入）：

    • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
    • listA - 第一个链表
    • listB - 第二个链表
    • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
    • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

    评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

     

    示例 1：

    输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

     

    示例 2：

    输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

    示例 3：

    输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

     

    提示：

    • listA 中节点数目为 m
    • listB 中节点数目为 n
    • 1 <= m, n <= 3 * 104
    • 1 <= Node.val <= 105
    • 0 <= skipA <= m
    • 0 <= skipB <= n
    • 如果 listA 和 listB 没有交点，intersectVal 为 0
    • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

     

    进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

    思想：

    1. 指针的地址是唯一的。所以当遍历到相交结点时，指针的地址重复，即是相交的结点，返回这个结点。

    2. 注意不能用指针的值返回，指针的值相同不代表是相交链表。

    3.不能同时都从头开始遍历，这样会错开导致无法在相交结点相遇。 

    注意点 

    单链表是不存在 x型交叉，因为单链表是只有一个next指针。

     所以下图的情况是不可能出现的。

    相交的情况只可能是下图情况

     

    第一步先求两个链表的长度

    1.     while(fast->next!=NULL){
    2.         i++;
    3.         fast = fast->next;
    4.     }
    5.     while(slow->next!=NULL){
    6.         j++;
    7.         slow = slow ->next;
    8.     }

    第二步 让长的先走，当长短一样时一起走。

    这里的意思是，先假设headA是longhead，在判断如果不是那么将headB设置为longhead，然后在让longhead先走。

    1.  //长的先
    2.     int n = abs(i-j);//abs是C语言求绝对值函数
    3.     struct ListNode* longhead = headA;
    4.     struct ListNode* shorthead = headB;
    5.     if(j>i){
    6.         longhead = headB;
    7.         shorthead = headA;
    8.     } 
    9.     while(n--)
    10.     {
    11.         longhead = longhead->next;
    12.     }
    13.     while(longhead!=shorthead)
    14.     {
    15.         longhead = longhead->next;
    16.         shorthead = shorthead->next;
    17.     }
    犯错点

     

        if(i>j){

            while(n--)

            {

                headA = headA->next;

            }

        }else if(i==j){

            headA = headA->next;

            headB = headB->next;

        }else{

             while(n--)

            {

                headB = headB->next;

            }

        }

        while(headA!=headB){

            headA = headA->next;

            headB = headB->next;

        }

        return headA;

    }

    紫色的这句话是多余的，因为如果两个链表长度相等时，n为0，那么那么就不用进入while（）循环，所以不用写。写了会导致和 while(headA!=headB)重复

     

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     struct ListNode *next;
    6.  * };
    7.  */
    8. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    9.     struct ListNode* fast = headA;
    10.     struct ListNode* slow = headB;
    11.     int i = 1;
    12.     int j = 1;
    13.     //求长
    14.     while(fast->next!=NULL){
    15.         i++;
    16.         fast = fast->next;
    17.     }
    18.     while(slow->next!=NULL){
    19.         j++;
    20.         slow = slow ->next;
    21.     }
    22.     if(fast!=slow)
    23.     {
    24.         return NULL;
    25.     }
    26.     //长的先
    27.     int n = abs(i-j);//abs是C语言求绝对值函数
    28.     /*struct ListNode* longhead = headA;
    29.     struct ListNode* shorthead = headB;
    30.     if(j>i){
    31.         longhead = headB;
    32.         shorthead = headA;
    33.     } 
    34.     while(n--)
    35.     {
    36.         longhead = longhead->next;
    37.     }
    38.     while(longhead!=shorthead)
    39.     {
    40.         longhead = longhead->next;
    41.         shorthead = shorthead->next;
    42.     }*/
    43.     if(i>j){
    44.         while(n--)
    45.         {
    46.             headA = headA->next;
    47.         }
    48.     }else{
    49.          while(n--)
    50.         {
    51.             headB = headB->next;
    52.         }
    53.     }
    54.     while(headA!=headB){
    55.         headA = headA->next;
    56.         headB = headB->next;
    57.     }
    58.     return headA;
    59. }

     

     

     第二题 判断是有环

    141. 环形链表

    简单

    相关标签

    相关企业

    给你一个链表的头节点 head ，判断链表中是否有环。

    如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

    如果链表中存在环 ，则返回 true 。 否则，返回 false 。

    示例 1：

    输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

    示例 2：

    输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

    示例 3：

    输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

     思想：

    用快慢两个指针，慢指针一次走1步，快指针一次走2步。当他们两的地址相同时就是出现了环。

     注意

    1.循环条件，如果无环的话，会出现两种情况，一种是fast==NULL，一种fast->next==NULL;

     

     

    1. /**
    2.  * Definition for singly-linked list.
    3.  * struct ListNode {
    4.  *     int val;
    5.  *     struct ListNode *next;
    6.  * };
    7.  */
    8. bool hasCycle(struct ListNode *head) {
    9.     struct ListNode* fast = head;
    10.     struct ListNode* slow = head;
    11.     while(fast!=NULL&&fast->next!=NULL){
    12.         slow = slow->next;
    13.         fast = fast->next->next;
    14.         if(fast==slow){
    15.             return true;
    16.         }
    17.     }
    18.     return false;
    19. }
    错误分享

     这里return false不能放在 while里，因为链表一开始fast也不等于slow，这样循环刚开始就返回false。应该放在循环体外。

    第三题（重点面试题）

     

    142. 环形链表 II

    中等

    相关标签

    相关企业

    给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

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

    不允许修改 链表。

    示例 1：

    输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

    示例 2：

    输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

    示例 3：

    输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

     思路：

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

    用meet记录下他们相遇的点。

    利用结论L = N*C - X，设置一个指针指向起点，meet指向相遇的点。他们两同时出发，会在环入口出相遇，输出相遇时的点。

     

    1. struct ListNode *detectCycle(struct ListNode *head) {
    2.     struct ListNode* fast = head;
    3.     struct ListNode* slow = head;
    4.     struct ListNode* phead = head;
    5.     while(fast!=NULL&&fast->next!=NULL)
    6.     {
    7.         slow = slow->next;
    8.         fast = fast->next->next;
    9.         if(slow==fast)
    10.         {
    11.             struct ListNode* meet = slow;
    12.             while(phead!=meet)
    13.             {
    14.                 meet = meet->next;
    15.                 phead = phead->next;
    16.             }
    17.             return meet;
    18.         }
    19.        
    20.     }
    21.     return 0;
    22. }

     这题面试问题🧐😎🤓🫠⭐

     第一题 为什么他们会在入口出相遇

            答：因为结论 L = N*C -X ,L是起点到入口的距离，N是快指针在环内走了圈数，C是环长，X是入口到相遇点的距离。

    第二题 L = N*C -X 怎么得来的

     

    第三题 slow一次走一步，fast一次走2步一定会相遇吗

            答：一定会相遇。当他们之间的距离N=0时就会相遇

     

    第四题 slow一次走1步，fast一次走三步会相遇吗

    答        当N为偶数时，直接就追上了

                 当N为奇数时，C为奇数时，第二轮可以追上

                 当N为奇数时，C为偶数时，永远追不上 

    第五题 slow一次走n步，fast一次走m步可以追上吗

    答        ：若N%（m-n）==0 可以追上。

     

  • 相关阅读:
    Java Web概述
    LVS+Keepalived群集
    【附源码】Python计算机毕业设计图书销售管理系统
    韦东山D1S板子——xfel工具无法烧写bin文件到spi norFlash问题解决
    值得你收藏的Notes应用模板
    【ARM Cortex-M 系列 4 番外篇 -- 常用 benchmark 介绍】
    网络安全（黑客）自学
    ChatGPT搭建AI网站实战
    html标签中crossOrigin、integrity属性详解
    ESP01S通过心知天气获取天气和时间信息
  • 原文地址：https://blog.csdn.net/qq_62830324/article/details/134520063