寻找环形链表的入环点

之前我们在判断一个链表是否为环， 是运用快慢指针的方法，且只能是慢指针走一步，快指针两步；

那么如何求带环链表的入环点的
思路一：数学方法（找出带环链表各个特点量的关系）

代码：

struct ListNode *detectCycle(struct ListNode *head) {
//快慢指针判断是否为环
    struct ListNode *slow;
    struct ListNode *fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)//相遇点
        {
            struct ListNode *meet=fast;//定义一个相遇点指针
            while(head!=meet)
            {
                head=head->next;
                meet=meet->next;
            }
            return head;
        }

    }
    return NULL;//不为环，就没有入环点返回空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路2：转换法，转化为求两个链表的交点，

代码：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
   
    struct ListNode *cur1=headA;
    struct ListNode *cur2=headB;
    int long1=1;
    int long2=1;
    //找到两链表的尾节点，并算数各自的长度
    while(cur1->next)
    {
        cur1=cur1->next;
        long1++;
    }
     while(cur2->next)
    {
        cur2=cur2->next;
        long2++;
    }
    //如果尾节点不相等，就不会相交
    if(cur1!=cur2)
    {
        return NULL;
    }
    //abs函数求出绝对值（两节点的长度差）
    int k=abs(long1-long2);
//假设法找到巧妙运用到长节点
   struct ListNode *longList=headA;
   struct ListNode *shortList=headB;
   if(long1<long2)
   {
         longList=headB;
         shortList=headA;
   }
   //长的先走k步
   while(k--)
   {
       longList=longList->next;
   }
   //一起走
   while(longList!=shortList)
   {
       longList=longList->next;
       shortList=shortList->next;
   }
   //返回交点longList或shortList
   return longList;

}
struct ListNode *detectCycle(struct ListNode *head) {
//快慢指针判断是否为环
    struct ListNode *slow;
    struct ListNode *fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)//相遇点
        {
            struct ListNode *newhead=slow->next;
            slow->next=NULL;
            struct ListNode *meet=getIntersectionNode(head,newhead);//求两链表的交点
            return meet;
        }

    }
    return NULL;//不为环，就没有入环点返回空
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67