关于leetcode个人解题总结:刷题8找出两个链表的交点

Leetcode: 160. 相交链表
两种解法：双指针法和哈希表法。

1. 双指针法

思路：链表 A 和 B 同时登程，链表 A 走到开端，跳到 B 的结尾持续走，B 走到开端，同样跳到 A 持续走，如果 A，B 不相等，继续执行，如果 A，B 相等，有两种可能：①A=B=null，A 和 B 都来到了各自的开端，A，B 无交点。②A=B= 链表交点，该状况 A，B 存在交点，这时返回 A，B 任一节点即可。因而如果两个链表相交，返回的值是两链表第一个交点，如果不相交，返回的是 null。

// 双指针法
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headA == null)  return null;
        ListNode A = headA,B = headB; 

        while(A!= B){
            A = A == null?headA:A.next;
            B = B == null?headB:B.next;
        }

        return A;
    }
}

2. 哈希表法

（1）如果指向链表的指针 A 或者 B 任何一个为空，则没有交点，返回 null
（2）把链表 A 所有节点退出先 hashset
（3）遍历链表 B，在遍历过程中的节点如果在 hashset 中存在，则阐明该节点为公共节点，如果最终遍历完没有节点存在 hashset 中，两链表不相交，则返回空。

// 哈希表法
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if(headA == null || headB == null) return null;
        HashSet<ListNode> set = new HashSet<ListNode>();

        while(headA != null){set.add(headA);
            headA = headA.next;
        }

        while(headB != null){if(set.contains(headB)){return headB;}
            headB = headB.next;
        }

        return null;
    }
}