Solving data structure problems may be tough for a beginner. You look at the problem and a question arises: where do I start? Recently I was solving a problem of finding an intersection of two linked lists. After analyzing the problem I came up with a solution, which I explain below.
Task
Your task is to write a program to find the node at which the intersection of two singly linked lists begins. You may not modify original input (assume there is no cycle in the list).
One possible solution is to go over first list and remember all nodes you visited. You can use Set() structure to store nodes as you visit them. Then, go over the second list and for every node, check if it is in the set. If the check is positive, this is the beginning of lists intersection.
//node function Node(value) {
// this.value = value;
// this.next = null;
//}//Time complexity: linear
//Memory complexity: linear const findIntersectionNode = function(headA, headB) { let currentHeadA = headA
let currentHeadB = headB let mySet = new Set()
while (currentHeadA !== null) {
mySet.add(currentHeadA)
currentHeadA = currentHeadA.next
}
while (currentHeadB !== null) {
if (mySet.has(currentHeadB)) {
return currentHeadB
}
currentHeadB = currentHeadB.next
} return null
}
