leetcode-160-相交链表

相交链表

题面

leetcode题目

给你两个单链表的头节点 \(headA\) 和 \(headB\) ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 \(null\) 。

图示两个链表在节点 \(c1\) 开始相交：
题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

example

示例1图片

输入：\(intersectVal = 8\), \(listA = [4,1,8,4,5]\), \(listB = [5,0,1,8,4,5]\), \(skipA = 2\), \(skipB = 3\)
输出：Intersected at '8'
解释：相交节点的值为 \(8\) （注意，如果两个链表相交则不能为 \(0\)）。
从各自的表头开始算起，链表 \(A\) 为 \([4,1,8,4,5]\)，链表 \(B\) 为 \([5,0,1,8,4,5]\)。
在 \(A\) 中，相交节点前有 \(2\) 个节点；在 \(B\) 中，相交节点前有 \(3\) 个节点。

数据范围

• listA 中节点数目为 \(m\)
• listB 中节点数目为 \(n\)
• \(0 \leq m\), \(n \leq 3\times 10^4\)
• \(1 \leq Node.val \leq 10^5\)
• \(0 \leq skipA \leq m\)
• \(0 \leq skipB \leq n\)

如果 \(listA\) 和 \(listB\) 没有交点，\(intersectVal\) 为 \(0\)
如果 \(listA\) 和 \(listB\) 有交点，\(intersectVal == listA[skipA + 1] == listB[skipB + 1]\)

题解

总体思路

这个题如果第一次见到会比较麻。我们先考虑链表相交的情况: 我们考虑将链表A与链表B头尾虚拟的连接起来，也就是链表A尾部的\(5\)节点连接到链表B的\(5\)节点，链表B尾部的\(5\)节点连接到链表A的\(4\)节点，这样我们从A的头节点开始遍历会得到\([4,1,8,4,5,5,0,1,8,4,5,\cdots]\)这样的序列，同理我们从B的头节点开始遍历会得到\([5,0,1,8,4,5,4,1,8,4,5,\cdots]\)序列。我们考虑A链表和B链表相交的部分有\(c\)个节点，A链表的不相交部分有\(a\)个节点，B链表的不相交部分有\(b\)个节点。
同时开始遍历，第一轮A和B到达相交节点分别走了\(a\)，\(b\)步，第二轮A和B到达相交节点分别走了\(a+c+b\)，\(b+c+a\)步，因为\(a+c+b = b+c+a\)，所以此时已经同时到达了相交节点。
考虑链表不相交的情况，我们还是继续遍历，第一轮A和B经过\(a\),\(b\)步后到达了尾节点，继续遍历第二轮A和B经过\(a+b\)，\(b+a\)步后到达了尾节点，此时A和B同时到达尾节点，可以判定不相交。

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <cstring>
using namespace std;

#define _NDEBUG
/**
 * 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 *p1 = headA;
        ListNode *p2 = headB;
        bool switchA, switchB;
        switchA = switchB = false;
        if (p1 == NULL || p2 == NULL)
        {
            return NULL;
        }
        while (p1 != NULL || p2 != NULL)
        {
            if (p1 == p2)
            {
                return p1;
            }
            if (p1 == NULL)
            {
                if (switchA)
                {
                    p1 = headA;
                }
                else
                {
                    p1 = headB;
                }
                switchA = !switchA;
            }
            else
            {
                p1 = p1->next;
            }
            if (p2 == NULL)
            {
                if (switchB)
                {
                    p2 = headB;
                }
                else
                {
                    p2 = headA;
                }
                switchB = !switchB;
            }
            else
            {
                p2 = p2->next;
            }
        }
        return NULL;
    }
};

// for test
int main()
{
    Solution s;

    return 0;
}