Good evening! Here's our prompt for today.
Assume you have a Linked List implementation that has the following API:
JAVASCRIPT
1// prepend to start of list
2#prepend(val);
3
4// appends to end of list
5#append(val);
6
7// get an array of node values (for testing)
8#toArray();Can you write a method getIntersection(list1, list2) to find the intersection of two linked lists?
The return value should be a new linked list.
Constraints
- Length of the two linked lists <=
1000 - The nodes in the list will always contain integer values between
-1000000000and1000000000 - Expected time complexity :
O(n*m)(the lengths of the two lists) - Expected space complexity :
O(n)
Try to solve this here or in Interactive Mode.
How do I practice this challenge?
xxxxxxxxxx98
function getIntersection(list1, list2) { // fill in implementation for method return;}// Supporting data structuresclass LinkedList { constructor() { this.head = null; this.tail = null; } prepend(newVal) { const currentHead = this.head; const newNode = new Node(newVal); newNode.next = currentHead; this.head = newNode; if (!this.tail) { this.tail = newNode; } } append(newVal) { const newNode = new Node(newVal); if (!this.head) { this.head = newNode; this.tail = newNode; } else { this.tail.next = newNode; this.tail = newNode; } } isPresent(val) { let head = this.head; while (head) { if (head.val === val) { return true; } head = head.next; } return false; } toArray() { const toPrint = []; let currNode = this.head; while (currNode) { toPrint.push(currNode.val); currNode = currNode.next; } return toPrint; } toString() { const toPrint = []; let currNode = this.head; while (currNode) { toPrint.push(currNode.val); currNode = currNode.next; } return toPrint.join(' -> '); }}function Node(val) { this.val = val; this.next = null;}try { let list1 = new LinkedList(); list1.prepend(25); list1.prepend(15); list1.prepend(5); list1.prepend(9); let list2 = new LinkedList(); list2.prepend(14); list2.prepend(15); list2.prepend(7); list2.prepend(13); assertSameMembers(getIntersection(list1, list2).toArray(), [15]); console.log( 'PASSED: Getting the insection of two lists with node `15` should return a list of `15`.' );} catch (err) { console.log(err);}function assertSameMembers(a, b) { return JSON.stringify(a.sort()) === JSON.stringify(b.sort());}OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
Here's how we would solve this problem...
How do I use this guide?
Access all course materials today
The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.
