《链表篇》---相交链表

用户11288958

发布于 2024-10-24 08:46:39

4130

文章被收录于专栏：学习学习

题目链接

相交链表

方法一：哈希集合

判断两个链表是否相交。使用哈希集合存储链表节点。创建一个哈希Set集合。先将链表A中的节点放入这个集合中。再遍历链表B。如果哈希集合中存在链表B中的节点。那么此时就是相交状态。

代码实现：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while(temp != null){
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while(temp!=null){
            if(visited.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

方法二：双指针

使用双指针的方法，可以将空间复杂度降至 O(1)。

pA 从链表 headA 的头部开始遍历，pB 从链表 headB 的头部开始遍历。
如果 pA 到达了链表 headA 的末尾（pA == null），就让它跳到链表 headB 的头部继续遍历。
同理，如果 pB 到达了链表 headB 的末尾（pB == null），就让它跳到链表 headA 的头部继续遍历。
当 pA 和 pB 相等时，说明找到了相交的节点；如果两个指针都到达了末尾（null），说明没有相交的节点。

当 pA 到达链表headA的末尾时，pA 被重置为链表headB的头部，这是为了让 pA 开始遍历链表headB。类似地，当 pB 到达链表headB的末尾时，pB 被重置为链表headA的头部。通过这种方式，两个指针在遍历完自己的链表后，会从对方的链表头开始遍历。由于两个指针都会遍历两个链表的总长度，无论两个链表的长度是否相同，最终两个指针会在相交节点处相遇，或者同时到达链表的末尾（即没有相交节点的情况）。

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

        while(pA != pB){
            if(pA == null){
                pA = headB;
            }else{
                pA = pA.next;
            }

            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }