[Leetcode]返回链表开始入环的第一个节点

力扣链接

思路一:快慢指针法

一个指针从相遇点走,一个指针从起始点走,会在入口点相遇.

最终代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow,* fast;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;


        if(slow == fast)
        {
            struct ListNode* meet = slow;
            struct ListNode* start = head;


            while(meet != start)
            {
                meet = meet->next;
                start = start->next;
            } 
            return meet;


        }
    }
    return NULL;
}

思路二:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//两个链表的交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {


    struct ListNode* tailA = headA,* tailB = headB;
    int lenA = 1, lenB = 1;
    while(tailA->next)
    {
        tailA = tailA->next;
        ++lenA; 
    }
    while(tailB->next)
    {
        tailB = tailB->next;
        ++lenB;
    }
    if(tailA != tailB)
    {
        return NULL;
    }


    int gap = abs(lenA - lenB);
    struct ListNode* longList = headA,* shortList = headB;
    if(lenA<lenB)
    {
        longList = headB;
        shortList = headA;
    }
    while(gap--)
    {
        longList= longList->next;
    }


    while(longList !=shortList)//比较的是地址
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;


}




struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode *slow,* fast;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;


        if(slow == fast)
        {
            //转换成lt1和lt2求交点
            struct ListNode* meet = slow;
            struct ListNode* lt1 = meet->next;
            meet->next = NULL;
            struct ListNode* lt2 = head;


            return getIntersectionNode(lt1,lt2);


        }
    }
    return NULL;
}