数据结构链表力扣例题AC（3）—

数据结构链表力扣例题AC（3）——代码以及思路记录

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

AC写法一

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    //思路基本一样
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int lenA = 0,lenB = 0;
    //先计算两个的长度
    while(curA)
    {
        curA = curA->next;
        lenA++;
    }
    while(curB)
    {
        curB = curB->next;
        lenB++;
    }
    //遍历结束后回到头结点
    curA = headA;
    curB = headB;
    //计算差距，并开始走差距步,diff大小可以知道哪一个更长
    int diff = lenA - lenB;
    if(diff > 0) {
        while(diff > 0) {
            curA = curA->next;
            diff--;
        }
    } else if(diff < 0) {
        while(diff < 0) {
            curB = curB->next;
            diff++;
        }
    }
    //当两个不相等就继续走，但是要注意任意一个都不能为空
    while(curA && curB && curA != curB)
    {
        curA = curA->next;
        curB = curB->next;
    }
    //如果没有相交，两个也都走到了空
    //如果相交了此刻停留的位置也正好是相交初始节点，直接返回
    return curA;
}

AC写法二

struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int lenA = 0,lenB = 0;
    //lenA和lenB最后计数都会少了一个
    //但这道题目的是为了计算差值
    //同时都少一个不会对结果有影响
    while(curA->next)
    {
        curA = curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB = curB->next;
        lenB++;
    }
    //如果尾节点不相同，就没有相交。直接返回
    if(curA != curB)
    {
        return NULL;
    }
    //abs函数，计算绝对值
    int n = abs(lenA - lenB);
    struct ListNode* longList = headA, *shortList = headB;
    //上一步做了假设，如果假设不成立那就交换，后边就不用关心长的是哪条链表了
    if(lenB > lenA)
    {
        longList = headB;
        shortList = headA;
    }
    //长的先走差距步
    while(n--)
    {
        longList = longList->next;
    }
    while(longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    return longList;

代码思路

上述两种代码的基本思路是一样的，具体细微的差别已经标注在代码中，接下来进行陈述：

首先看题寻找相交节点，那么这个链表不可能是 X 型，因为节点只能存储一个节点地址，所以只能是 Y 型或者不想交是平行，这一点看题目就可以明白。

最容易想到的暴力法，双指针，一个指向链表A，一个指向链表B，lenA进行链表A的遍历，将每一个节点与lenB当前所指的节点进行比较看是否相等，都不相等则lenB指向下一个LenA再进行比较，这样的方法时间复杂度为O(N^2)

还有一种时间复杂度为O(N)的方法。观察 Y 型结构，假设有两个指针指向两条链表的开始同时开始走并进行比较，由于链表相交前长度可能不一样，不一样的时候两个指针不可能相遇，但如果要两个指针相遇，相交之前有部分必须对应，那现在就是解决如何使两个指针按照我们需要的对应起来了，当较长的链表先走，走到剩余部分和较短链表一样时，两个指针一起走就解决了这个问题，而这部分先走的就是两条链表的长度差，所以两个指针都遍历一遍链表得出各自长度（遍历的同时可以比较尾节点是否相同，不相同直接说明没有相交），然后相减得出长度差，就可以实现如有交点两个指针一定会相遇的情况了。

141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。否则，返回 false 。

AC

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow = head, * fast = head;

    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;

        if(slow == fast){
            return true;
        }
    }
    return false;
}

代码思路

快慢指针绝绝绝绝绝绝！

环形链表难点在于不知道哪里开始的环，但是在环里，就没有前后之分，使用快慢指针，从头开始走，fast走两步slow走一步，当fast走进环的时候slow一定还在后边，但是当slow也进环以后，由于两者速度不一样，fast会追上slow，想象一下速滑运动中的套圈，而在环中的话，就一定会相遇。如果没有环，那么fast会指向空。只要思路正确并不难写。至于为什么while循环中还需要fast->next也不能为空，因为fast一次走两步，当fast指向尾节点的时候，没有fast->next->next.

为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

快指针一次走3步，走4步，...n步行吗？

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

AC

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* slow = head, *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;
}