【142. 环形链表 II】

---

一、题目描述

题目链接

---

二、做题思路

思路一：公式证明

思路二：当不知道推导的公式时
相遇时一定在圈里，它是尾节点
以相交链表的思想去做

思路三：

---

三、题目代码

思路一：公式证明

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */
struct ListNode *detectCycle(struct ListNode *head) {
    
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    struct ListNode * meet = NULL;
    while(fast && fast->next)
    {
    
        fast=fast->next->next;
        slow=slow->next;
        if(fast == slow)
        {
    
            meet = fast;
           while(head != meet)
           {
    
             head=head->next;
             meet=meet->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 *tail) {
    
    struct ListNode * listA = headA;
    struct ListNode * listB = headB;
    int lenA=1;int lenB=1;
    while(listA!=tail)
    {
    
        listA=listA->next;
        lenA++;
    }
    while(listB!=tail)
    {
    
        listB=listB->next;
        lenB++;
    }
    if(listA != listB)
    {
    
        return NULL;
    }
    int gap=abs(lenA-lenB);
    struct ListNode * longlist = headA;
    struct ListNode * shortlist = headB;
    if(lenA < lenB)
    {
    
        longlist = headB;
        shortlist = headA;
    }
    while(gap--)
    {
    
        longlist=longlist->next;
    }
    while(longlist != shortlist)
    {
    
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return shortlist;
}
struct ListNode *detectCycle(struct ListNode *head) {
    
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    struct ListNode * meet = NULL;
    while(fast && fast->next)
    {
    
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
    
            meet=slow;
            struct ListNode * newhead = meet->next;
            struct ListNode * p=getIntersectionNode(newhead,head,meet);
            return p;
        }
    }
   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 * listA = headA;
    struct ListNode * listB = headB;
    int lenA=1;int lenB=1;
    while(listA->next)
    {
    
        listA=listA->next;
        lenA++;
    }
    while(listB->next)
    {
    
        listB=listB->next;
        lenB++;
    }
    if(listA != listB)
    {
    
        return NULL;
    }
    int gap=abs(lenA-lenB);
    struct ListNode * longlist = headA;
    struct ListNode * shortlist = headB;
    if(lenA < lenB)
    {
    
        longlist = headB;
        shortlist = headA;
    }
    while(gap--)
    {
    
        longlist=longlist->next;
    }
    while(longlist != shortlist)
    {
    
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return shortlist;
}
struct ListNode *detectCycle(struct ListNode *head) {
    
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    struct ListNode * meet = NULL;
    while(fast && fast->next)
    {
    
        slow=slow->next;
        fast=fast->next->next;
        if(fast==slow)
        {
    
            meet=slow;
            struct ListNode * newhead = meet->next;
            meet->next=NULL;
            struct ListNode * p=getIntersectionNode(newhead,head);
            return p;
        }
    }
   return NULL;
}

---

以上是本篇文章的全部内容，如果文章有错误或者有看不懂的地方，多和喵博主交流。互相学习互相进步。如果这篇文章对你有帮助，可以给喵博主一个关注，你们的支持是我最大的动力。