相交链表

1.LeetCode原题地址

2.解法思路一：暴力求解，这个是很简单的，内嵌遍历循环就可以了，最开始想到的就这这种办法，由于for循环自带空值判定，所以不需要判断也可以

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        for(;headA!=null;headA = headA.next)
        {
            ListNode temp = headB;
            for(;temp!=null;temp = temp.next)
            {
                if(headA==temp)
                    return headA;
            }
        }
        return default;
    }
}

3.解法思路二：双指针遍历，由于headA和headB的节点数是不相等了，但是在第一次相交后，节点数是必定相同的，因为保持了相同的引用，这是一种非常巧妙的解法，但是理解起来有点难，特别是双指针必定相交原因，强烈安利这位题主的解题思路，非常清晰

时间复杂度 O(a + b)O(a+b) ：最差情况下（即 |a - b| = 1∣a−b∣=1 , c = 0c=0 ），此时需遍历 a + ba+b 个节点。
空间复杂度 O(1)O(1) ：节点指针 A , B 使用常数大小的额外空间。

160. 相交链表（双指针，清晰图解） - 相交链表 - 力扣（LeetCode）

经典判空
设置俩个临时变量储存AB俩个节点
进行循环变量，跳出条件是tempA==tempB
tempA节点和tempB节点同时向后移动，链表跑完则从头继续跑，长短链表都如此，此时考虑俩种情况
- 有相交点：有交点则必定会相遇，就像俩个人在操场跑圈，俩个人从不同的起跑点出发，可能速度有慢有快，但只要一直跑，总会相遇，这种问题类似于快慢指针的问题。
- 无相交点：这就是这个解法有意思的地方，即使没有相交点，最后也是会相遇的，不过这个相交点变成了最后俩个人的结束点，也就是tempA == tempB == null，所以不会陷入死循环；

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == default || headB == default)
            return default;

        ListNode tempA = headA;
        ListNode tempB = headB;
        while(tempA!=tempB)
        {
            tempA = tempA!=null ? tempA.next : headA;
            tempB = tempB!=null ? tempB.next : headB;
        }
        return tempA;
    }
}