142. Linked List Cycle II

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findMeetringPoint(ListNode* head) {
        ListNode *tortoise = head, *hare = head;
        while (hare->next && hare->next->next){
            tortoise = tortoise->next;
            hare = hare->next->next;
            if (tortoise == hare) return tortoise;
        }
        return NULL;
    }

    ListNode *getCycle(ListNode* head, ListNode* meetingPoint) {
        ListNode *p1 = head, *p2 = meetingPoint;
        while (p1 != p2) {
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }

    ListNode *detectCycle(ListNode *head) {
        if (!head || !head->next) return NULL;

        ListNode *meetingPoint = findMeetringPoint(head);
        if (!meetingPoint) return NULL;

        return getCycle(head, meetingPoint);
    }
};

判断单链表是否存在环，判断两个链表是否相交

当fast若与slow相遇时，slow肯定没有走遍历完链表，而fast已经在环内循环了n圈(1<=n)。假设slow走了s步，则fast走了2s步（fast步数还等于s 加上在环上多转的n圈），设环长为r，则：

2s = s + nr

s= nr

设整个链表长L，入口环与相遇点距离为x，起点到环入口点的距离为a。

a + x = nr

a + x = (n – 1)r +r = (n-1)r + L - a

a = (n-1)r + (L – a – x)

(L – a – x)为相遇点到环入口点的距离，由此可知，从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点，于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点。

#include <stdio.h>
#include <stdlib.h>
typedef struct node{
    int value;
    struct node *next;
}LinkNode,*Linklist;

/// 创建链表(链表长度，环节点起始位置)
Linklist createList(){
    Linklist head = NULL;
    LinkNode *preNode = head;
    LinkNode *FifthNode = NULL;
    for(int i=0;i<6;i++){
        LinkNode *tt = (LinkNode*)malloc(sizeof(LinkNode));
        tt->value = i;
        tt->next = NULL;
        if(preNode == NULL){
            head = tt;
            preNode = head;
        }
        else{
            preNode->next =tt;
            preNode = tt;
        }

        if(i == 3)
            FifthNode = tt;
    }
    preNode->next = FifthNode;
    return head;
}

///判断链表是否有环
LinkNode* judgeRing(Linklist list){
    LinkNode *fast = list;
    LinkNode *slow = list;

    if(list == NULL)
        return NULL;

    while(true){
        if(slow->next != NULL && fast->next != NULL && fast->next->next != NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        else
            return NULL;

        if(fast == slow)
            return fast;
    }
}

///获取链表环长
int getRingLength(LinkNode *ringMeetNode){
    int RingLength=0;
    LinkNode *fast = ringMeetNode;
    LinkNode *slow = ringMeetNode;
    for(;;){
        fast = fast->next->next;
        slow = slow->next;
        RingLength++;
        if(fast == slow)
            break;
    }
    return RingLength;
}

///获取链表头到环连接点的长度
int getLenA(Linklist list,LinkNode *ringMeetNode){
    int lenA=0;
    LinkNode *fast = list;
    LinkNode *slow = ringMeetNode;
    for(;;){
        fast = fast->next;
        slow = slow->next;
        lenA++;
        if(fast == slow)
            break;
    }
    return lenA;
}

///环起始点
///如果有环, 释放空空间时需要注意. 
LinkNode* RingStart(Linklist list, int lenA){
    if (!list || lenA <= 0){
        return NULL;
    }

    int i = 0;
    LinkNode* tmp = list;
    for ( ; i < lenA; ++i){
        if (tmp != NULL){
            tmp = tmp->next;
        }
    }

    return (i == lenA)? tmp : NULL;
}

///释放空间
int freeMalloc(Linklist list, LinkNode* ringstart){
    bool is_ringstart_free = false; //环起始点只能被释放空间一次
    LinkNode *nextnode = NULL;

    while(list != NULL){
        nextnode = list->next;
        if (list == ringstart){ //如果是环起始点
            if (is_ringstart_free)
                break;  //如果第二次遇到环起始点addr, 表示已经释放完成
            else
                is_ringstart_free = true;   //记录已经释放一次
        }
        free(list);
        list = nextnode;
    }

    return 0;
}

int main(){
    Linklist list = NULL;
    LinkNode *ringMeetNode  = NULL;
    LinkNode *ringStartNode = NULL;

    int LenA       = 0;
    int RingLength = 0;

    list = createList();
    ringMeetNode = judgeRing(list); //快慢指针相遇点

    if(ringMeetNode == NULL)
        printf("No Ring\n");
    else{
        printf("Have Ring\n");
        RingLength = getRingLength(ringMeetNode);   //环长
        LenA = getLenA(list,ringMeetNode);

        printf("RingLength:%d\n", RingLength);
        printf("LenA:%d\n", LenA);
        printf("listLength=%d\n", RingLength+LenA);
    }

    ringStartNode = RingStart(list, LenA);  //获取环起始点
    freeMalloc(list, ringStartNode);    //释放环节点, 有环时需要注意. 采纳5楼建议
    return 0;
}https://i.stack.imgur.com/7Ootm.png

Proof of Floyd Cycle Chasing (Tortoise and Hare)

If the preliminary tail is lengthTTand the cycle is lengthCC(so in your picture,T=3T=3,C=6C=6), we can label the tail nodes (starting at the one farthest from the cycle) as−T,−(T−1),...,−1−T,−(T−1),...,−1and the cycle nodes0,1,2,...,C−10,1,2,...,C−1(with the cycle node numbering oriented in the direction of travel).

We may use the division algorithm to writeT=kC+rT=kC+rwhere0≤r<C0≤r<C.

AfterTTclicks the tortoise is at node00and the hare is at noderr(since hare has gone2T2Tsteps, of which the firstTTwere in the tail, leavingTTsteps in the cycle, andT≡r(modC)T≡r(modC)).

Assumingr≠0r≠0, after an additionalC−rC−rclicks, the tortoise is at nodeC−rC−r; and the hare is at node congruent(modC)(modC)tor+2(C−r)=2C−r≡C−r(modC)r+2(C−r)=2C−r≡C−r(modC). Hence both critters are at nodeC−rC−r. [In ther=0r=0case, you can check that the animals meet at the node00.]

The distance from the start at this meeting time is thusT+C−r=(kC+r)+C−r=(k+1)CT+C−r=(kC+r)+C−r=(k+1)C, a multiple of the cycle length, as desired. We can further note, this occurrence is at the first multiple of the cycle length that is greater than or equal to the tail length.