This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Cross linked list

Write a program to find the start node where two singly linked lists intersect.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Reference of the node with value = 8 Reference of the node with value = 8 Starting from their respective table headers, linked list A is [4,1,8,4,5] and linked list B is [5,0,1,8,4,5]. In A, there are two nodes before the intersecting node; In B, there are three nodes before the intersection node.Copy the code

Example 2:

Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 Reference of the node with value = 2; Reference of the node with value = 2; Starting from their respective table headers, linked list A is [0,9,1,2,4] and linked list B is [3,2,4]. In A, there are three nodes before the intersecting node; In B, there is 1 node before the intersecting node.Copy the code

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 output: null From their respective headers, linked list A is [2,6,4] and linked list B is [1,5]. Because the two linked lists do not intersect, intersectVal must be 0, and skipA and skipB can be arbitrary values. Explanation: The two lists do not intersect, so null is returned.Copy the code

Pay attention to

  • If two lists do not intersect, null is returned.
  • After the result is returned, both lists must remain in their original structure.
  • It can be assumed that there are no loops in the entire list structure.
  • The program meets the O(n) time complexity as far as possible and uses only O(1) memory.

Thought analysis

When you first look at this problem, it’s easy to think of a violent solution, going through the for loop; Another solution is to use HashSet to store one of the linked lists, and then determine whether the other list also has; O(n){O(n)}O(n) time complexity, and only O(1){O(1)}O(1) memory, so neither of the above solutions can be used (but the HashSet solution is provided at the end).

Create two Pointers pA and pB to be initialized as the headers of linked list A and B, respectively. And then let them go back node by node. When pApA reaches the end of the list, reposition him to the head of list B (you read that right, list B); Similarly, when pB reaches the end of the list, it is repositioned to the head of list A. If pA and pB meet at some point, they are intersecting nodes.

The code shown

Double needle method, the time complexity is O (n) (n)} {O O (n), space complexity is O (1) (1)} {O O (1).

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        ListNode one = headA;
        ListNode two = headB;
        int count = 0;
        while(one ! = two){if(one ! =null){
                one = one.next;
            } else {
                // There is no need, because in the end if both are null, the loop will also be broken
// if (count == 1){
// return null;
/ /}
// count++;
                one = headB;
            }

            if(two ! =null){
                two = two.next;
            } else{ two = headA; }}return one;
    }
Copy the code

HashSet solution is as follows:

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // Time O(n), space O(n)
        Set<ListNode> set = new HashSet<>();
        ListNode p = headA;
        while(p ! =null){
            set.add(p);
            p = p.next;
        }
        p = headB;
        while(p ! =null) {if (set.contains(p)){
                return p;
            }
            p = p.next;
        }
        return null;
Copy the code

conclusion

Using brute force and HashSet is something many people can think of, but it is not easy to satisfy both the time complexity O(n){O(n)}O(n) and the space complexity O(1){O(1)}O(1), so the two-pointer solution is the only solution.