相交链表+判断环型链表+求环型链表的入口节点

一.相交链表

相交链表

相交：两个链表从头开始遍历，尾节点一定是同一个节点。

情况一：当两个链表长度相同时：

情况二：当两个链表长度不同时：

思路：

1. 求两个链表长度的差值gap。
2. 让长链表先走gap个节点。
3. 分别遍历两个链表，比较是否为同一个节点，若是则相交，否则不相交。

代码如下：

typedef struct ListNode ListNode;

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    ListNode* la = headA;
    ListNode* lb = headB;
    int lengthA = 0, lengthB = 0;
    while(la)
    {
        lengthA++;//求链表A的长度
        la = la->next;
    }
    while(lb)
    {
        lengthB++;//求链表B的长度
        lb = lb->next;
    }
    //求链表A与链表B长度差的绝对值
    int gap = abs(lengthA - lengthB);

    //找出长链表与短链表
    ListNode* longList = headA;
    ListNode* shortList = headB;
    if(lengthB > lengthA)
    {
        longList = headB;
        shortList = headA;
    }

    //让长链表先走gap个节点
    while(gap--)
    {
        longList = longList->next;
    }

    //此时longList与shortList指针在相对的位置上（同时遍历链表为NULL）
    //判断两个链表是否相交
    while(longList && shortList)
    {
        if(longList == shortList)
        {
            //链表相交
            return longList;
        }
        //两个指针继续往后走
        longList = longList->next;
        shortList = shortList->next;
    }
    //链表不相交
    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

二.判断环型链表

环型链表

思路：快慢指针，即慢指针一次⾛一步，快指针一次走两步，两个指针从链表起始位置开始行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的未尾。

思考1：为什么快指针每次走两步，慢指针走一步可以相遇，有没有可能遇不上，请推理证明！

因此，在带环链表中慢指针走一步，快指针走两步最终一定会相遇。

思考2：快指针一次走3步，走4步，…n步行吗?

思考：真的存在N是奇数，C是偶数这一条件？？？

下面给出等式：

代码如下：

1. 慢指针一次走一步，快指针一次走两步

typedef struct ListNode ListNode;

bool hasCycle(struct ListNode* head)
{
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next)
    {
        //慢指针一次走一步，快指针一次走两步
        slow = slow->next;
        fast = fast->next->next;
        //当慢指针 == 快指针时，有环
        if (slow == fast)
        {
            return true;
        }
    }
    //无环
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2. 慢指针一次走一步，快指针一次走三步：

typedef struct ListNode ListNode;

bool hasCycle(struct ListNode *head) 
{
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next && fast->next->next)
    {
        //慢指针一次走一步，快指针一次走三步
        slow = slow->next;
        fast = fast->next->next->next;
        //当慢指针 == 快指针时，有环
        if(slow == fast)
        {
            return true;
        }
    }
    //无环
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

三.求环型链表的入口节点

环型链表 ||

思路：快慢指针，快指针一次走两步，慢指针一次走一步，若为环型链表最终在环中相遇，然后让一个指针从相遇点开始走，一个指针从起点开始走，一次走一步，最终在进环处相遇。

代码如下：

//解：快慢指针，快指针一次走两步，慢指针一次走一步,若为环型链表最终在环中相遇
 //    然后让一个指针从相遇点开始走，一个指针从起点开始走，一次走一步，最终在进环处相遇

typedef struct ListNode ListNode;

struct ListNode* detectCycle(struct ListNode* head)
{
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            //有环
            ListNode* meet = slow;//相遇点
            while (meet != head)
            {
                //一个指针从相遇点开始走，一个指针从起点开始走，最终一定在入环点相遇
                head = head->next;
                meet = meet->next;
            }
            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

typedef struct ListNode ListNode;

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    ListNode* la = headA;
    ListNode* lb = headB;
    int lengthA = 0, lengthB = 0;
    while(la)
    {
        lengthA++;//求链表A的长度
        la = la->next;
    }
    while(lb)
    {
        lengthB++;//求链表B的长度
        lb = lb->next;
    }
    //求链表A与链表B长度差的绝对值
    int gap = abs(lengthA - lengthB);

    //找出长链表与短链表
    ListNode* longList = headA;
    ListNode* shortList = headB;
    if(lengthB > lengthA)
    {
        longList = headB;
        shortList = headA;
    }

    //让长链表先走gap个节点
    while(gap--)
    {
        longList = longList->next;
    }

    //此时longList与shortList指针在相对的位置上（同时遍历链表为NULL）
    //判断两个链表是否相交
    while(longList && shortList)
    {
        if(longList == shortList)
        {
            //链表相交
            return longList;
        }
        //两个指针继续往后走
        longList = longList->next;
        shortList = shortList->next;
    }
    //链表不相交
    return NULL;
}

struct ListNode *detectCycle(struct ListNode *head) 
{
    ListNode* slow = head;
    ListNode* fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            //有环
            ListNode* meet = slow;//相遇点
            ListNode* newHead = meet->next;
            meet->next = NULL;

            return getIntersectionNode(head, newHead); 
        }
    }
    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
68
69
70
71
72