Find the Intersection of Two Linked Lists

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Description

Assume you have a Linked List implementation that has the following API:

// prepend to start of list
#prepend(val);

// appends to end of list
#append(val);

// get an array of node values (for testing)
#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 -1000000000 and 1000000000
Expected time complexity : O(n*m) (the lengths of the two lists)
Expected space complexity : O(n)

```js
function getIntersection(list1, list2) {
  // implement a method to get the union
}

class 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.head = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  toArray() {
    const toPrint = [];
    let currNode = this.head;

    while (currNode) {
      toPrint.push(currNode.val);
      currNode = currNode.next;
    }

    return toPrint;
  }

  toString() {
    this.toArray().join(' ');
  }
}
```

CONTINUE WITH ALGODAILY PREMIUM

Keep going with the complete tutorial.

Unlock the remaining explanations and exercises, alongside the full learning library.

Explore Premium →

Open interactive view →