Day2-线性表-链表求环的起点

BUPTrenyi

发布于 2019-07-16 11:41:29

3920

发布于 2019-07-16 11:41:29

文章被收录于专栏：算法其实很好玩

一先致谢

第一天发文，就收到了上百关注，还是发自内心地感谢大家的~

二关于公众号留言的问题

我也纳闷啊，怎么就不能留言了呢？

查了一下，这才知道，新注册的公众号，确实是没有留言功能了

不过没关系，有疑问，或者有建议的同学，可以后台私信给我，我会在第二天的文章中一一作答，再次感谢~

三上题

不废话了，开始今天的盒饭

链表求环问题，和逆置一样，很经典，相信大部分同学手撸没啥问题，快慢指针嘛，所以今天和昨天一样，也来个升级版

Q：已知链表可能存在环，若有环，返回环的起点，没有返回NULL

四分析

首先对于这样的有环链表来说：

第一趟：slow到2，fast到3

第二趟：slow到3，fast到5

第三趟：slow到4，fast到7

第四趟：slow到5，fast到5

相遇了

然后呢，怎么求起点？

继续冷静分析：

slow指针走过路程：2,3,4,5

fast指针走过路程：2,3,4,5,6,7,4,5

将2,3,4段看作 a

将5段看作b

将6,7,4段看作c

那么就有：a+b+c+b = 2(a+b)

即 a=c

立即推：从head与meet出发，速度相同，相遇时，即为环起点

五完整代码及注释

//
// Created by renyi on 2019/5/30.
//
#include<iostream>
using namespace std;

struct Node{
    int value;
    Node* next;
    Node(int v):value(v),next(NULL){}
};

Node* findCycleMeet(Node* head){
    Node* fast = head;//初始化快、慢指针
    Node* slow = head;
    Node* meet = NULL;//初始化指向相遇节点的指针

    while (fast){
        slow = slow->next;//快慢指针先各走一步
        fast = fast->next;
        if (!fast){
            return NULL;//如果fast遇到了链表尾，则说明已遍历完，没相遇，即无环，返回null
        }
        fast = fast->next;//fast再走一步
        if (fast == slow){
            meet = fast;//记录相遇节点
            break;
        }
    }

    while (head && meet){
        if (head == meet){//当head与meet相遇，则说明遍历到了环起点
            return head;
        }
        head = head->next;//head和meet各走一步
        meet = meet->next;
    }
}

int main(){
    Node a(1);
    Node b(2);
    Node c(3);
    Node d(4);
    Node e(5);
    Node f(6);
    Node g(7);

    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    g.next = &d;

    Node* node = findCycleMeet(&a);
    if (node){
        printf("have cycle,and the start node is:%d\n", node->value);
    } else{
        printf("not have cycle");
    }

    return 0;
}

注意：第55行，我将第7个节点后继，指向了第4个节点，故最终应输出4