Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

Given the head node of two linked lists, determine whether the two lists intersect. If they do, return the start node of the intersection, otherwise return null.

Their thinking

Each entry will determine whether the node is already in the Set. If the node is already in the Set, the current node will be returned directly. If both lists have been traversed, null will be returned.

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

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

The time complexity of the code is O(n)O(n)O(n) O(n)O(n)O(n) O(n)O(n). So they want the space to be O(1)O(1)O(1), so the other way to think about it is, we don’t need extra space.

In this case, it is only necessary to ensure that the two lists keep the same length to move backward. Each step after that, it is determined whether the two nodes are the same. If they are the same, it is the intersection point. The specific process is as follows:

First, calculate the length of the two lists respectively, then determine which one is long and calculate the difference between the two lists. After the long list goes the distance of difference, the two lists can go at the same time, and the code is as follows:

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        while(curA! =null){
            curA = curA.next;
            lenA++;
        }
        while(curB! =null){
            curB = curB.next;
            lenB++;
        }
        int preStep = lenA-lenB;
        if(preStep>0) {while(preStep>0){ headA = headA.next; preStep--; }}else if(preStep<0) {while (-preStep>0){ headB = headB.next; preStep++; }}while(headA! =null&&headB! =null) {if(headA==headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
Copy the code

The time complexity of the above code is O(n)O(n)O(n) O(n), and the space complexity is O(1)O(1)O(1).

There is also a method that does not need to calculate the length of the two linked lists, and can eliminate the influence of the inconsistent length of the two linked lists by moving them:

Set two Pointers preA and preB to point to headA and headB respectively, and let preA and preB move simultaneously. When one pointer reaches null, the remaining distance of the other pointer is the length difference between the two linked lists. At this point, the completed pointer points to the other pointer, and the unfinished pointer points to the other linked list. In this case, the length of the linked list can be the same as that of the two Pointers, and then you can judge as you walk backwards. 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

The time complexity is O(n)O(n)O(n), and the space complexity is also O(1)O(1)O(1).