160. 相交链表

160. 相交链表

hash表解法：

时间复杂度：O(2n)
空间复杂度：O(2n)

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            // - 使用Hash集合存储链表中的节点
            Set<ListNode> set = new HashSet<ListNode>();

            // - 查找相交链表不能改变原链表，因此初始化两个临时引用
            ListNode temp = headA;
            ListNode cur = headB;

            // - 循环遍历链表A 先将存储在Hash表中
            while (null != temp) {
                set.add(temp);
                temp = temp.next;
            }

            // - 如果链表B 中的节点有存在Hash集合中，则链表相交 返回相交的节点
            while (null != cur) {
                if (set.contains(cur)) {
                    return cur;
                }
                cur = cur.next;
            }
            // - 否则返回null
            return null;

        }
    }

双指针解法：

时间复杂度：O(n)
空间复杂度：O(2n)

    public class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

            // - 首先进行边界判断
            if(null == headA || null == headB){
                return null;
            }

            // - 初始化两个指针 分别指向 链表A 和 链表B
            ListNode pointA = headA;
            ListNode pointB = headB;
            // - 思路：循环遍历：链表A + 链表B  和 链表B + 链表A 是否存在相交的节点
            // - 相交的时候跳出
            while (pointA != pointB){
                if(null == pointA){
                    // - 如果链表A 结束 让指针指向链表B
                    pointA = headB;
                } else {
                    // - 指针向后移动
                    pointA = pointA.next;
                }

                if(null == pointB){
                    // - 如果链表B 结束 让指针指向链表A
                    pointB = headA;
                } else {
                    // - 指针向后移动
                    pointB = pointB.next;
                }
            }
            // - 此处返回链表A 还是链表B 都可以
            return pointA;


        }
    }