【leetcode题解C++】160.相交链表 and 142.环形链表

?160.相交链表

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

图示两个链表在节点?c1?开始相交：

题目数据?保证?整个链式结构中不存在环。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。

在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例?2：

输入：intersectVal?= 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出：Intersected at '2'

解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。

在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例?3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出：null

解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。

由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。

这两个链表不相交，因此返回 null 。

思路：用两个指针分别管理两个链表，要想相交后的内容是相同的，那么两个可能长度不相同的链表在各自某一结点后的长度需要是相同的，所以可以把长的链表的指针走到与短的链表头结点对齐，再来判断后续内容是否相同。那么，首先计算长度，然后对齐链表，再判定。（下方的代码中多出了判断长度，然后把长的链表当作A的过程，是为了在后续省下对链表长度判断的代码）。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA = headA;
        ListNode *curB = headB;
        int lenA = 0, lenB = 0;
        while(curA != nullptr) {
            ++lenA;
            curA = curA->next;
        }
        while(curB != nullptr) {
            ++lenB;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        if(lenB > lenA) {
            swap(lenA, lenB);
            swap(curA, curB);
        }
        int gap = lenA - lenB;
        while(gap--) {
            curA = curA->next;
        }
        while(curA != nullptr && curB != nullptr) {
            if(curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return nullptr;
    }
};

?142.环形链表

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

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

不允许修改?链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例?2：

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

思路1：注意到，看到重复的结点，那么就知道是环了，如此一来，unordered_set解决。

代码实现1：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> record;
        while(head != nullptr) {
            if(record.count(head)) {
                return head;
            }
            record.insert(head);
            head = head->next;
        }
        return nullptr;
    }
};

思路2：参考到了代码随想录，转化为一个快慢指针的追及问题——在快慢指针在环内相遇之后，记录当前的index，然后再用一个指针从头结点往后搜索环的入口（和index相遇就是入口）。

代码实现2：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //追及问题
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while(fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast) {
                ListNode *index = fast;
                ListNode *enterSearch = head;
                while(index != enterSearch) {
                    enterSearch = enterSearch->next;
                    index = index->next; 
                }
                return enterSearch;
            }
        }
        return nullptr;
    }
};