数据结构

02-29 1926阅读 0评论

一. 判断单链表有无环

a. 错误的思路：遍历陷入死循环

1）和相交的遍历思路一样，找指向相同。

$数据结构,数据结构,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,地址,最后,关系,第1张$

（图片来源网络，侵删）

错误点

一直在死循环。

思考点：如何破环

b. 个人思路：反转链表回首结点

1）目前的经验，无非就是增删查改，反转链表，快慢指针，于是一个个靠；

2）发现，反转有环链表后，会回到首结点。

图解思路如图1:

图1 反转有环链表大体流程

增益点：反转破环

反转链表可以跳出环的死循环。

$数据结构,数据结构,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,地址,最后,关系,第3张$

（图片来源网络，侵删）

代码

typedef struct ListNode Node;
bool hasCycle(struct ListNode* head) {
    if (head == NULL)
        return false;
    Node* n1 = NULL;
    Node* n2 = head;
    Node* n3 = NULL;
    while (n2)
    {
        n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
    }
    if (n1 == head && head->next != NULL) 回到首结点就是有环
        return true;
    return false;
}

c. 参考思路：快慢指针转为追及问题

1）环相当于初中还是高中的一道物理题：在学校操场上，小狗速度是小猫的两倍，问小狗多久能追上小猫。即快指针为慢指针速度的两倍；

2）速度为两倍的考究点为，2-1=1，保证每次只追一个结点距离，实现追及结点遍历，避免陷入奇偶死循环的局面。

增益点：思路本身和二倍速度遍历所有结点

代码

typedef struct ListNode Node;
bool hasCycle(struct ListNode *head) {
    if(head==NULL||head->next==0)
    return false;
    Node* fast=head;
    Node* slow=head;
    Node* n3=NULL;
    while(fast)
    {
        fast=fast->next;
        if(fast)
        fast=fast->next;
        slow=slow->next;
        if(slow==fast)
        return true;
    }
    return false;
}

二. 有环，返回入环结点地址

a. 个人思路一：继续反转链表找思路（缺陷就是无用遍历多了些）

1）发现在反转思路出环的状态会出现一个反向新环；

2）遍历反向新环得到入环结点地址。

图解思路如图2:

![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/0fece3bbcb534614928f194064a0a681.png#pic_center

$数据结构,数据结构,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,地址,最后,关系,第5张$

（图片来源网络，侵删）

图2 反转过程形成的反向新环

图中，对应反转后的一次移位，利用这个反向新环的任意一结点store去遍历这个环，如果与n1地址相同，则n1为入环地址。

未解决的问题：编译器对的，oj不对

编译器结果如图3:

图3 编译器的监视窗口数据

从图中可以看出，store是找到了n1，并返回了n1的地址。

oj结果如图4:

图4 oj输出

输出是这没环？我编译器一步一步调试都是对的，还找到了入环结点，怎么到你这就找不到了？而且最开始思考的图解思路也是没错的。

代码

typedef struct ListNode Node;
struct ListNode* detectCycle(struct ListNode* head) {
    if (head == NULL)
        return NULL;
    Node* n1 = NULL;
    Node* n2 = head;
    Node* n3 = NULL;
    Node* store = NULL;
    while (n2)
    {
        n3 = n2->next;
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if (n3)
            n3 = n3->next;
        store = n1;
        while (store)     没环一定到NULL，有环就一直循环直到找到n1
        {
            store = store->next;
            if (store == n1)
                return n1;
           
        }
    }
    return NULL;
}

b . 个人思路二：快慢指针公式求解，没做出来

列出未知数，如图5：

图5 快慢指针追及图

其中x为入环前跳数，y为慢指针入环后跳数，z为剩余跳数。

1）慢指针跑不了一个环，则x+y可知；

2）相遇后，再次跑一圈可以得到环的结点数：z+y+1。

3）快指针跳数：x+y+nz（n未知）;

4）慢指针跳数：x+y；

5）二倍速，中点数量关系：2*（x+y）=x+y+n*(y+z+1)。

四个未知数，三个等式，求不出来。

c . 参考思路一：未知数n无所谓

看成：

C=y+z+1;环结点数

2*（x+y）=x+y+nC;

x=C-y+(n-1)C;

可以看作，C-y是跑了(n-1)C的圈后的最后一圈位置。

(n-1)C相当于是白跑了(n-1)圈，不必知道n的具体大小。即从快慢指针相遇点出发一定能和head出发相遇

增益点：无，过于具体题目具体分析了

代码

typedef struct ListNode Node;
struct ListNode * detectCycle(struct ListNode *head) {
    if (head == NULL)
        return NULL;
    Node* slow = head;
    Node* fast = head;
    Node* store = NULL;
    while(fast)
    {
        fast=fast->next;
        if(fast)
         fast=fast->next;
        slow=slow->next;
        if(slow==fast)
        break;
    }
    if(fast!=slow)
    return NULL;
    store= slow;
    while(head!=store)
    {
        head=head->next;
        if(store)
        store=store->next;
    }
    return store;
}