一. 题目

二. 思路

1. 额外容器标记

• 先遍历链表A并存入容器。

• 再遍历链表B，判断是否当前节点在容器中，若在就是交叉节点。

• 时间复杂度O(m+n), 空间复杂度O(m)

2. 变值法

• 先遍历链表A，并将值设为其相反数(val范围>=1)。

• 再遍历链表B，遇到值为-1的就是交叉节点。

• 最后恢复所有修改的值。

• 时间复杂度O(m+n), 空间复杂度O(1)

3. 双指针

三. 代码

2. 变值法

class ListNode
{
    int val;
    ListNode next;

    ListNode(int x)
    {
        val = x;
        next = null;
    }
}

class Solution
{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB)
    {
        ListNode pA = headA;//记录A的头
        while (headA != null)//变值
        {
            headA.val = -headA.val;
            headA = headA.next;
        }

        ListNode ans = null;
        while (headB != null)//找交叉节点
        {
            if (headB.val < 0)
            {
                ans = headB;
                break;
            }
            headB = headB.next;
        }

        while (pA != null)//恢复原值
        {
            pA.val = -pA.val;
            pA = pA.next;
        }

        return ans;
    }
}

3. 双指针

class ListNode
{
    int val;
    ListNode next;

    ListNode(int x)
    {
        val = x;
        next = null;
    }
}

class Solution
{
    public ListNode getIntersectionNode(ListNode headA, ListNode headB)
    {
        if (headA == null || headB == null)
        {
            return null;
        }

        ListNode pA = headA, pB = headB;
        while (pA != pB)
        {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}