preface

This problem will be solved in two ways: hash tables and double Pointers

  • The first idea is to use a hash table to store all the nodes in one list and see if the nodes in the other list exist in the hash table
  • After looking at the leetcode solution, you can also use double Pointers to solve this problem. The space complexity is better, it goes straight to constant order O(1). The general idea is to have two Pointers traverse each node of two linked lists in different directions.

1. Title 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. See leetcode address for a detailed description of the topic

Second, the problem solving

2.1 Hash table solution

2.1.1 ideas

  • Store all the nodes of one of the linked lists into a hash table
  • Access all nodes of another list to see if there are nodes of another list in the hash table

2.1.2 code

Git code address

Const gettionNode = function(headA, headB) { Could not cross the if (headA = = = null | | headB = = = null) return null / / hash table const set = new set () / / temporary variables, Let temp = headA; let temp = headA; Temp == null) {set.add(temp) temp = temp.next} If (set.has(temp)) return temp = temp.next} return temp}Copy the code

2.2 Two-pointer solution

2.2.1 ideas

  • Create two Pointers p and q
  • These two Pointers traverse each node of both lists
  • The two Pointers traverse from different points of view: each starts from a different list
  • Traversal encounter indicates intersection
  • If the two Pointers do not meet at the end of traversal, they do not intersect. Both Pointers point to NULL, so return one of them

2.2.2 code

const getIntersectionNode = function(headA, Any headB) {/ / list is empty, could not cross the if (headA = = = null | | headB = = = null) return null / / create a double pointer p, q, respectively from different head node, Let p = headA let q = headB // p, q are not equal. == q) {p = p == null; // The pointer q traverses the list starting with headB and the list starting with headA q = q === null? HeadA: q.ext} // if p is a node and p is null if p is not a node, return p};Copy the code