Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

preface

Data structure and algorithm belong to the internal work of the developer, no matter how the front-end technology changes, how the framework updates, how the version iteration, it is the same content. Always remember in the byte youth training camp, moon shadow teacher said a word, do not ask front-end learning algorithm. Everyone in computer science needs to know about algorithms and has the subconscious to write high-quality code.

I. Problem description

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 linked lists do not intersect, null is returned.

The two linked lists intersect 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.

Custom benchmarks:

The input to the evaluation system is as follows (your program does not apply to this input) :

  • IntersectVal – specifies the value of intersecting starting node. This value is 0 if there are no intersecting nodes
  • ListA – First linked list
  • ListB – Second linked list
  • SkipA – The number of nodes in the listA that jump to the cross node (starting from the head node)
  • SkipB – The number of nodes in the listB that jump to the cross node (starting from the head node)
  • The profiling system creates a chained data structure based on these inputs and passes the two head nodes, headA and headB, to your program. If the program returns the intersecting nodes correctly, your solution will be considered the correct answer.

Example 1:

Enter: intersectVal =8, listA = [4.1.8.4.5], listB = [5.6.1.8.4.5], skipA = 2, skipB = 3Output: Intersected at'8'Interpretation: The value of the intersection node is8(Note that if two lists intersect, it cannot be0). Starting from the respective table headers, linked list A is [4.1.8.4.5], linked list B is [5.6.1.8.4.5]. In A, we have theta before the intersecting node2A node; In B, we have theta before the intersecting node3A node.Copy the code

Example 2:

Enter: intersectVal =2, listA = [1.9.1.2.4], listB = [3.2.4], skipA = 3, skipB = 1Output: Intersected at'2'Interpretation: The value of the intersection node is2(Note that if two lists intersect, it cannot be0). Starting from the respective table headers, linked list A is [1.9.1.2.4], linked list B is [3.2.4]. In A, we have theta before the intersecting node3A node; In B, we have theta before the intersecting node1A node.Copy the code

Example 3:

Enter: intersectVal =0, listA = [2.6.4], listB = [1.5], skipA = 3, skipB = 2Output:nullFrom the respective table headers, linked list A is [2.6.4], linked list B is [1.5]. Because the two linked lists do not intersect, intersectVal must be0, and skipA and skipB can be arbitrary values. The two lists do not intersect, so returnnull 。
Copy the code

Tip:

  • The number of nodes in listA is M
  • The number of nodes in the listB is N
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • If listA and listB do not intersect, intersectVal is 0
  • If there is an intersection between listA and listB, intersecting intersectVal == listA[skipA] == listB[skipB]

Second, the solution of the problem

2.1 Violent Solution

It was very direct and very violent. For each node in linked list A, it is enough to determine whether B exists. Time complexity O (N^2)

var getIntersectionNode = function(headA, headB) {
    if(! headA || ! headB)return null
    let p1 = headA
    while(p1){
        let p2 = headB // Iterate over each node in the first list
        while(p2){
            if(p1==p2) return p1
            p2 = p2.next
        }
        p1 = p1.next
    }
    return null
};
Copy the code

2.2 Hash table records

The solution is simple, iterate through the first list, store all the nodes in a hash table, iterate through the second list, and return as soon as the element is found in the hash table.

var getIntersectionNode = function(headA, headB) {
    if(! headA || ! headB)return null
    let map = new Map(a)let p1 = headA
    while(p1){
        map.set(p1,true)
        p1 = p1.next
    }
    let p2 = headB
    while(p2){
        if(map.has(p2)) return p2
        p2 = p2.next
    }
    return null
};
Copy the code

2.3 Two-pointer solution

Suppose list A is m distance from the intersecting nodes, and list B is N distance from the intersecting nodes. From the intersection node to the end of the list is x and then you have

  • HeadA: length = m + x
  • HeadB: length = n + x

If the end of two linked lists are joined together, that is, headA = headA –> headB, headB = headB –> headA, the two linked lists will arrive at the intersection node after iterating once

Soul painter Little White HHH

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

subsequent

  • Address: Intersecting linked list

Well, this link is the end of the intersecting chain list, I am Shao Xiaobai, a junior student in the front-end field, welcome to 👍 comments.