LeetCode: Merge Two Sorted Lists Solution

Approach

Keep iteratate two pointers, one for each list

Append smaller node to the dummy node on each iteration

Implementation (iterative)

1var mergeTwoLists = function (l1, l2) {
2  let dummy = (iter = new ListNode())
3
4  while (l1 && l2) {
5    if (l1.val < l2.val) {
6      iter.next = l1
7      l1 = l1.next
8    } else {
9      iter.next = l2
10      l2 = l2.next
11    }
12    iter = iter.next
13  }
14
15  // because the above loop stop when one of the list pointers is null
16  // so this line is to make sure we don't miss the last pointer
17  iter.next = l1 || l2
18
19  return dummy.next
20}

Implementation (recursive)

1var mergeTwoLists = function (l1, l2) {
2  if (!l1) return l2
3  if (!l2) return l1
4  if (l1.val < l2.val) {
5    l1.next = mergeTwoLists(l1.next, l2)
6    return l1
7  } else {
8    l2.next = mergeTwoLists(l1, l2.next)
9    return l2
10  }
11}

(Bonus) Implementation (break and rebuild)

Convert to arrays

Concat and sort

Build back to linked list

1var mergeTwoLists = function (l1, l2) {
2  const llistToArray = llist => {
3    let iter = llist
4    const res = []
5    while (iter) {
6      res.push(iter.val)
7      iter = iter.next
8    }
9    return res
10  }
11  const arrayToLlist = arr => {
12    let dummy = (iter = new ListNode())
13    arr.forEach(el => {
14      const node = new ListNode(el)
15      iter.next = node
16      iter = iter.next
17    })
18    return dummy.next
19  }
20
21  return arrayToLlist(
22    [...llistToArray(l1), ...llistToArray(l2)].sort((a, b) => a - b)
23  )
24}