链表oj3（Leetcode）——相交链表；环形链表

一，相交链表

相交链表（Leetcode）

1.1分析

看到这个我们首先想到的就是一个一个比较他们的值有相等的就是交点，但是如果a1和b2的值就相等呢？所以这个思路不行，第二种就是依次比较链表，但是这个方法也不行，因为两个链表长度不行不能这样比较。所以根据第二种的思路，我们可以先分别遍历两个链表然后找到长的那个，让它先走他们的差值步，最后再一起遍历，找到他们的交点。

1.2代码

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *curA=headA;
    struct ListNode *curB=headB;
    int lenA=1,lenB=1;
    //计算两个链表的长度
    while(curA->next)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }
    //不相交
    if(curA!=curB)
    {
        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 Longlist;
}
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

二，环形链表

环形链表（Leetcode）

2.1分析

这个题目我们可以用我们之前写过的一道oj题来解，那就是快慢指针。
主要思路就是，因为是环形链表他会一直的向前走，所以快指针循环到一定的程度他就一定会和慢的那个指针相遇。

2.2代码

bool hasCycle(struct ListNode *head) {
    struct ListNode *fast;
    struct ListNode *slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三，环形链表 II

环形链表 II（Leetcode）

3.1分析

这个题目和上面那个有点不同的是他要求我们返回入环的第一个节点。
我们先来进行数学分析。

然后我们就可直到从头开始走到入口，和从快慢指针相遇的地方开始走，那么他们相遇的位置就是入口。

3.代码

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

        if(slow == fast)
        {
            struct ListNode *meet=slow;
            while(head!=meet)
            {
                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