您现在的位置是：首页 >技术交流 >代码随想录算法训练营第四天|24. 两两交换链表中的节点 、19.删除链表的倒数第N个节点 、面试题 02.07. 链表相交 、142.环形链表II网站首页技术交流

面试题 02.07. 链表相交  

题目链接：力扣 

解题思路：
1、两次遍历，第一次用vector装链表A的节点，第二次遍历链表B中有没有A的节点，有则返回。
2、求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，此时就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap--) {
            curA = curA->next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

环形链表II

题目链接：力扣

思路：环形链表的题目都是有套路的，这题在剑指offer里做过，其中给的思路是：
首先确定是否有环：快慢指针，慢指针走一步，快指针走两步，若能相遇则有环；
其次确定环的大小，就在上一步相遇的地方一直找节点的next，直到重新回到开始的节点，记录环数为n；
最后快慢指针重新回到起点，快指针先走n步，再快慢指针同时走一步，直到相遇，相遇的点就是环形链表的入口节点。
附上我的代码：

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        ListNode* low = head;
        ListNode* quick = head;
        int CircleSize = 0;

        while(1)
        {
            if(low)
            {low = low->next;  cout<<"low go"<<endl;}   //慢指针走一步
            else
            break;

            if(quick && quick->next)
            {quick = quick->next->next; cout<<"quick go"<<endl;}   //快指针走两步
            else
            break;

            if(low == quick)    //此时说明有环，计算出环的大小
            {
                ListNode *start = low;
                CircleSize = 1;
                while((low =low->next) != start)
                 {
                     CircleSize++;
                 }
                 cout<<CircleSize<<endl;
                 break;               
            }

        }

        if(CircleSize > 0)           //有环时候的代码
        { 
            low = head;
            quick = head;
            while(CircleSize--)
                quick= quick->next;   //链表中环有n个节点，则快指针多走一n步
            while(low != quick)    //之后以相同的频率向前走
            {
                low = low->next;
                quick = quick->next;
            }
            return low;
        }

        return nullptr;
        
    }
};

卡哥给出另一种思路：
确定有环后，慢指针回到起点，快指针还在之前相遇的环上，接着快慢指针同时走一步，直到快慢指针重合就是环形链表的入口节点。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            // 快慢指针相遇，此时从head 和 相遇点，同时查找直至相遇
            if (slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while (index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2; // 返回环的入口
            }
        }
        return NULL;
    }
};