Merging Linked Lists

tags:Linked List Medium

Problem

You're given two Linked Lists of potentially unequal length. These Linked Lists potentially merge at a shared intersection node. Write a function that returns the intersection node or returns None / null if there is no intersection.
Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None null if it's the tail of the list.
Note: Your function should return an existing node. It should not modify either Linked List, and it should not create any new Linked Lists.

Sample Input

linkedListOne = 2 -> 3 -> 1 -> 4
linkedListTwo = 8 -> 7 -> 1 -> 4

Sample Output

// The lists intersect at the node with value 1
1 -> 4

---

Solutions

Official

Solution 1

1. choose one of the two lists to iterate through and create a set of all of the nodes
2. iterate through the other list, check to see if any of the nodes are in the first list

// O(n + m) time O(n) space - where n is the length of the
// first Linked List, and m is the length of the second Linked List
function mergingLinkedLists (linkedListOne, linkedListTwo) {
    const listOneNodes = new Set ();
    let currentNodeOne = linkedListOne;
    while (currentNodeOne !== null) {
        listOneNodes.add (currentNodeOne);
        currentNodeOne = currentNodeOne.next;
    }
    let currentNodeTwo = linkedListTwo;
    while (currentNodeTwo !== null) {
        if (listOneNodes.has (currentNodeTwo) ) return currentNodeTwo;
        currentNodeTwo = currentNodeTwo. next;
    }
    return null;
}

Solution 2

1. get the length of two lists
2. iterate the bigger list first to get two lists to the same length.
3. iterate over two lists,then it will reach the intersection point at the exact same time.

// O(n + m) time 0(1) space - where n is the length of the 
// first Linked List, and m is the length of the second Linked List
function mergingLinkedLists (linkedListOne, linkedListTwo) {
    let currentNodeOne = linkedListOne;
    let countOne = 0:
    while (currentNodeOne !== null) {
        countOne++;
        currentNodeOne = currentNodeOne.next;
    }

    let currentNodeTwo = linkedListTwo;
    let countTwo = 0;
    while (currentNodeTwo !== null) {
        countTwo++;
        currentNodeTwo = currentNodeTwo.next;
    }
    const difference = Math.abs(countTwo - countOne);
    let biggerCurrentNode = countOne > countTwo ? linkedListOne : linkedListTwo;
    let smallerCurrentNode = countOne > countTwo ? linkedListTwo : linkedListOne;

    for (let i = 0; 1 < difference; i++) {
        biggerCurrentNode = biggerCurrentNode.next;
    }
    while (biggerCurrentNode !== smallerCurrentNode) {
        biggerCurrentNode = biggerCurrentNode.next;
        smallerCurrentNode = smallerCurrentNode.next;
    }
    return biggerCurrentNode;
}

Solution 3

1. having both pointers go through both lists.

// O(n + m) time 0(1) space - where n is the length of the
// first Linked List, and m is the length of the second Linked List
function mergingLinkedLists (linkedListOne, linkedListTwo) {
    let currentNodeOne = linkedListOne;
    let currentNodeTwo = linkedListTwo;
    while (currentNodeOne !== currentNodeTwo) {
        if (currentNodeOne === null) {
            currentNodeOne = linkedListTwo;
        } else {
            currentNodeOne = currentNodeOne.next;
        }
        if (currentNodeTwo === null) {
            currentNodeTwo = linkedListOne;
        } else {
            currentNodeTwo = currentNodeTwo.next;
        }
    }
    return currentNodeOne;
}
// 2 -> 3 -> 8 -> 4
// 6 -> 8 -> 4

---

Everyone's

Iterate over the same list repeatedly

月

/* Time: O(m*n)
   Space: O(1)
*/
function mergingLinkedLists(linkedListOne, linkedListTwo) {
  let one = linkedListOne, two = linkedListTwo;
  while(one !== two){
    one = one ? one.next : linkedListOne;
    two = two ? two.next : linkedListTwo;
  }
  return one
}

Hao

/**
 * Time complexity: O(m*n) where n and m stands for linkedListOne.length, linkedListTwo.length respectly
 * Space complexity: O(1)
 */

function mergingLinkedLists(linkedListOne, linkedListTwo) {
  let curNodeOne = linkedListOne;
  let curNodeTwo = linkedListTwo;

  while (curNodeOne !== curNodeTwo) {
    if (curNodeOne === null) curNodeOne = linkedListOne;
    else curNodeOne = curNodeOne.next;

    if (curNodeTwo === null) curNodeTwo = linkedListTwo;
    else curNodeTwo = curNodeTwo.next;
  }

  return curNodeOne;
}

Solution3: iterate through another list

東

/* 
  Time O(m + n); Space O(1)
  m is the length of input linkedListOne
  n is the length of input linkedListTwo 
*/
function mergingLinkedLists(linkedListOne, linkedListTwo) {
  let currNodeOne = linkedListOne;
  let currNodeTwo = linkedListTwo;
  while(currNodeOne !== null || currNodeTwo !== null) {
    if(currNodeOne === null) currNodeOne = linkedListTwo;
    if(currNodeTwo === null) currNodeTwo = linkedListOne;
    if(currNodeOne === currNodeTwo) return currNodeOne;
    currNodeOne = currNodeOne.next;
    currNodeTwo = currNodeTwo.next;
  }
  return null;
}

YC

/*
  time: O(n) - where n is the sum of number of the nodes in both linked list
  space: O(1);
*/
function mergingLinkedLists(linkedListOne, linkedListTwo) {
  let pointOne = linkedListOne;
  let pointTwo = linkedListTwo;
  
  while(pointOne !== pointTwo){
    if(!pointOne) {
      pointOne = linkedListTwo;
    }
    else{
      pointOne = pointOne.next;
    }

    if(!pointTwo) {
      pointTwo = linkedListOne;
    }
    else{
      pointTwo = pointTwo.next;
    }
  }

  return pointOne;
}

---

Supplement / Discussion