“This is the 12th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

160. Intersecting linked lists

The title

Given the head nodes of two singly linked lists, headA and headB, find and return the start node where the two singly linked lists intersect. If two lists do not intersect, null is returned.

The graph shows two linked lists intersecting at node C1 ** : **

The problem data guarantees that there are no rings in the chain.

Note that after the function returns the result, the list must retain its original structure.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 output: Intersected at '8' The value of the intersection node is 8 (note that it cannot be 0 if two lists intersect). 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 output: Intersected at '2' The value of the intersection node is 2 (note that it cannot be 0 if two lists intersect). 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 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. The two lists do not intersect, so null is returned.Copy the code

Tip:

  • listAThe number of nodes ism
  • listBThe number of nodes isn
  • 0 <= m, n <= 3 * 10^4
  • 1 <= Node.val <= 10^5
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • iflistA 和 listBThere’s no intersection,intersectVal 为 0
  • iflistA 和 listBHave a intersection point,intersectVal == listA[skipA + 1] == listB[skipB + 1]

** Can you design a time complexity O(n) solution that uses O(1) memory only? Their thinking

Method 1: Use hash sets

  1. Iterate over linked list A and store the node to Set
  2. The linked list B is traversed to determine whether there is a current node in the Set. If there is, the node is the start node of the intersection
  3. If no intersection node is found after traversal, null is returned

Complexity analysis

  1. Time complexity: O(m + n), m and n are two linked list lengths respectively, and two linked lists need to be traversed, so the time complexity is O(m + n).
  2. Space complexity: O(m), m is the length of linked list A, which needs to use hash set to store all nodes of linked list A

Approach 2: Solution using O(1) memory

  1. If you concatenate list A to the tail of list B and list B to the tail of list A, then the two newly formed lists have the same lengthm + n(m and n are the lengths of the two lists respectively)
  2. If two list intersection, the new list have two “starting point”, and two new list of the second after the “starting point” have the same number of nodes And because the total length is the same, so the second before the “starting point” have the same number of nodes Therefore let two new list began to traverse the same time, to meet for the first time the same node, is the “starting point”
  3. If two linked lists do not intersect, the two new linked lists are traversed, null at the same time

Complexity analysis

  1. Time complexity: O(m + N), traversing the length of the splicing of two linked lists
  2. Space complexity: O(1)

Code 1

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}* /
var getIntersectionNode = function(headA, headB) {
    const set = new Set(a)let p = headA
    while (p) {
        set.add(p)
        p = p.next
    }
    p = headB
    while (p) {
        if (set.has(p)) {
            return p
        }
        p = p.next
    }
    return null
};
Copy the code

Code 2

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /

/ * * *@param {ListNode} headA
 * @param {ListNode} headB
 * @return {ListNode}* /
var getIntersectionNode = function(headA, headB) {
    if (headA === null || headB === null) {
        return null
    }
    let p1 = headA
    let p2 = headB
    while(p1 ! == p2) { p1 = p1 ==null ? headB : p1.next
        p2 = p2 == null ? headA : p2.next
    }
    return p1
};
Copy the code