单链表存在环的问题

心已赠人 2022-07-26 05:27 211阅读 0赞

# 问题 #

给定一个单链表，只给出头指针header

1.  判断链表是否存在环
2.  求环的长度
3.  求环的连接点
4.  求带环链表的长度

--------------------

// 简单的链表定义及生成带环链表函数
    typedef struct Node {
            struct Node *next;
    } node;
    
    node*  makeNode() {
            node * pNode = (node*)malloc(sizeof(node));
            pNode->next = NULL;
            return pNode;
    }
    typedef node* list;
    
    node* constructCircle() {
            list header = makeNode();
            node *pNode = header;
            node *pTmpNode = NULL;
            srand(time(NULL));
            int rnd = rand()%50;
            printf("rand value:%d\n", rnd);
            for (int i = 0; i < 50; i++) {
                    pNode->next = makeNode();
                    pNode = pNode->next;
                    if (i == rnd)
                        pTmpNode = pNode;
    
            }
            pNode->next = pTmpNode;
    
            return header;
    }

--------------------

// 1 判断链表是否存在环
    int isCircleExist(node *header) {
            node *slow = header;
            node *fast = header;
            // 通过判断fast指针，则不必判断slow指针
            while (fast != NULL && fast->next != NULL) {
                    fast = fast->next->next;
                    slow = slow->next;
                    if (slow == fast) {
                        return 1;
                    }
            }
    
            return 0;
    }

## fast指针步长选择 ##

### fast指针步长能不能选择3、4 或5等？ ###

能，fast指针步长可以选择3、4或5等其他步长。

### fast指针步长为什么选择2？ ###

--------------------

第二问证明：  
假设单链表的总长度为L，头结点到环入口的距离为a，环入口到快慢指针相遇的结点距离为x，环的长度为r，慢指针总共走了s步，则快指针走了2s步。另外，快指针要追上慢指针的话快指针至少要在环里面转了一圈多(假设转了n圈加x的距离)，得到以下关系：

s = a + x;
    2s = a + nr + x;
    =>a + x = nr;
    =>a = nr - x;

由上式可知：若在头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点。如下图所示：

![这里写图片描述][20160410201951313]

// 2 求环的长度
    int circleLength(node *header) {
            node *slow = header;
            node *fast = header;
            int i = 0, j = 0;
            int meet = 0;
            while (fast != NULL && fast->next != NULL) {
                    fast = fast->next->next;
                    slow = slow->next;
                    i = i+2;
                    j++;
                    if (slow == fast) {
                            meet++;
                            // 两指针第一次相遇，保证了他们已经在环内
                            if (meet == 1) {
                                    i = 0;
                                    j = 0;
                            }
                            // 两支针第二次相遇，则快指针比慢指针长走的长度刚好多一圈
                            if (meet == 2) {
                                    return i-j;
                            }
                    }
            }
    
            return 0;
    }

--------------------

// 3 求环的连接点
    node* findCirclePort(node *header) {
            node *slow = header;
            node *fast = header;
            while (fast != NULL && fast->next != NULL) {
                    fast = fast->next->next;
                    slow = slow->next;
                    if (slow == fast) {
                            break;
                    }
            }
            if (fast == NULL || fast->next == NULL)
                    return NULL;
            slow = header;
            while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
            }
            return slow;
    }

--------------------

// 4 求带环链表的长度
    int listLengthWithCircle(node *header) {
            node *port = findCirclePort(header);
            int len = 0;
            node *p = header;
            while (p->next != port) {
                    len++;
                    p = p->next;
            }
    
            len += circleLength(header);
            return len;
    }

# 参考 #

[判断一个单链表是否有环及环的链接点][Link 1]

[20160410201951313]: /images/20220724/3ac6799ea4894ea38ca7587726474b40.png
[Link 1]: http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html