Subject to introduce

Force buckle 160 questions: leetcode-cn.com/problems/in…

Method one: hash storage method

To determine whether two lists intersect, hash sets can be used to store list nodes.

First, the list headA is iterated and each node in the list headA is added to the hash set. We then iterate over the linked list headB and, for each node traversed, determine if the node is in the hash set:

If the current node is not in the hash set, the next node is traversed;

If the current node is in the hash set, then all subsequent nodes are in the hash set, that is, all nodes from the current node are at the intersection of the two lists, so the first node in the hash set traversed in the list headB is the node where the two lists intersect, and that node is returned.

If all nodes in linked list headB are not in the hash set, the two lists do not intersect and null is returned.

The code is as follows:

/** * 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) {
        if(headA == null || headB == null) {
            return null;
        }

        Map<ListNode,Integer> dataMap = new HashMap<>();
        ListNode tempA = headA;
        while(tempA ! =null) {
            dataMap.put(tempA,1);
            tempA = tempA.next;
        }
        ListNode tempB = headB;
        while(tempB ! =null) {
            if(dataMap.containsKey(tempB)) {
                return tempB;
            }          
            tempB = tempB.next;
        }   
        return null; }}Copy the code

Complexity analysis

  • Time complexity: O(m+n), where m and n are the lengths of linked list headA and headB respectively. You need to traverse both lists once.

  • Spatial complexity: O(m), where M is the length of linked list headA. A hash set is required to store all the nodes in the linked list headA.

Method two: double pointer

According to the question, if two lists intersect, then the length after the point of intersection is the same

All we need to do is have both lists traverse from the same distance at the end of the same distance. This position can only be the head of a shorter list. To do this, we must eliminate the length difference between the two lists

  • The Pointers pA to A and pB to B are traversed backwards
  • If pA reaches the end, pA = headB continues traversal
  • If pB reaches the end, then pB = headA continues traversal
  • When a longer pointer points to the head of a shorter list, the length difference is eliminated, so you only need to traverse the shortest list twice to find the position

It might sound a little convoluted, but the diagrams are the most intuitive, and the linked lists are the best for diagrams

Conclusion: the two Pointers must travel the same distance.

The code is as follows:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode pA = headA, pB = headB;
    while(pA ! = pB) { pA = pA ==null ? headB : pA.next;
        pB = pB == null ? headA : pB.next;
    }
    return pA;
}
Copy the code