526互联

【交叉链表】Java哈希表——HashSet类/双指针

发布时间 2023-12-13 13:30:48作者: 沙汀鱼

leetcode 160. 相交链表

题意：给定两个链表A、B的表头节点，找到链表交叉节点（地址值相同）。链表A长度为m，链表B长度为n，范围在[1, 3e4]

题解1：
根据哈希表去重的原理，使用哈希表集合HashSet来维护链表节点，默认比较节点地址值。将链表A中的节点全部add进HashSet中，然后遍历链表B中的节点，如果发现某节点在HashSet存在则找到交叉节点。

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

HashSet实现代码 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while(headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null) {
            if(set.contains(headB)) {
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

题解2：
维护链表A指针pA，链表B指针pB
这两个指针分别从链表头开始往后遍历，遍历到表尾后则指向另一个链表头继续遍历，直至找到交叉节点，或者两个指针同时再次遍历到表尾。
PS：当两个指针都指向另一个链表时，就表明，两个指针当前所在位置距离表尾的长度是一致的，通过这种方式可以消除两个链表长度不统一。

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

双指针实现代码 
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pA = headA, pB = headB;
        while(pA != null || pB != null) {
            if(pA == pB) return pA;
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return null;
    }
}