Leetcode Easy Linked List question: Why is my solution wrong? (21. Merge 2 sorted lists)

Question

Question:
Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
My solution:
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

My output is just 1->4 instead of 1->1->2->3->4->4. Can anyone please tell me why?

trincot · Accepted Answer

The main cause of the problems you encounter is in the third parameter that your function has: this is not in line with the description of the challenge. There is no third parameter. You need to create the returned list without such a value.
I understand that you have tried to pass a partial result as the third argument, and want to extend that partial result in each recursive call, but then things go wrong:
First, in the first two if blocks you assume that l3 is not null, but you cannot be sure of that. In case the input consists of an empty list, your code will produce an exception.
Secondly, if l3 represents a list that has more than one element, then this code will overwrite the existing link between l3 and l3.next, and so the original l3.next (and all the nodes that follow) will get lost.
Although you can solve this, by first finding the terminating node in l3, there is a better way. And this better way is actually a core principle in well designed recursion:
If possible, don't pass a partial result to the recursive call with the aim to extend that partial result to a final result. Instead try to make the function in such a way, that it does not need any such partial result from the caller, but can do its work on the input as if that was the very original input. The caller should use the returned value to treat that as a partial result, and extend it before returning that to its caller.


function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

// Helper function for demo
const listFromArray = a => a.length ? new ListNode(a[0], listFromArray(a.slice(1)))  
                                    : null;

let l1 = listFromArray([1, 2, 4]);
let l2 = listFromArray([1, 3, 4]);
console.log(mergeTwoLists(l1, l2));

kapil pandey · Answer

Your answer is returning only 1->4 because you are not iterating your newly created merged list i.e l3. You are directly doing l3.next=somevalue. Since l3 is a list you first need to iterate over it and add the value or list in its last node where l3.next will be null.
Here is the code which should give you the desired result


function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}
var mergeTwoLists = function(l1, l2, l3) {
  let addToMergedList = (l3, val) => {
    let rootNode = l3
    while (l3.next !== null)
      l3 = l3.next;
    l3.next = new ListNode(val);
    return rootNode;
  }
  if (l2 === null) {
    let root = l3
    if(!root)
      return l1
    while (l3.next)
      l3 = l3.next;
    l3.next = l1;
    return root;
  }
  if (l1 === null) {
    let root = l3
    if(!root)
     return l2
    while (l3.next)
      l3 = l3.next;
    l3.next = l2;
    return root;
  }
  if (l2.val < l1.val) {
    if (l3) {
      l3 = addToMergedList(l3, l2.val)
    } else {
      l3 = new ListNode(l2.val)
    }
    return mergeTwoLists(l1, l2.next, l3)
  } else {
    if (l3) {
      l3 = addToMergedList(l3, l1.val)
    } else {
      l3 = new ListNode(l1.val);
    }
    return mergeTwoLists(l1.next, l2, l3)
  }
};

let l1={val:1,next:{val:2,next:{val:4,next:null}}}
let l2={val:1,next:{val:3,next:{val:4,next:null}}
console.log(mergeTwoLists(l1, l2))

Emma · Answer

You can use a Sentinel Node so that it'd be much easier:
const mergeTwoLists = function(l1, l2) {
    const sentinel = {
        val: -1,
        next: null
    }

let head = sentinel
    while (l1 && l2) {
        if (l1.val > l2.val) {
            head.next = l2
            l2 = l2.next
        } else {
            head.next = l1
            l1 = l1.next
        }
        
        head = head.next
    }

head.next = l1 || l2

return sentinel.next
}

If you'd like to do recursively, we won't be needing an l3:
const mergeTwoLists = function(l1, l2) {
    if (l1 === null) {
        return l2
    }

if (l2 === null) {
        return l1
    }

if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1

} else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    }
}

Leetcode Easy Linked List question: Why is my solution wrong? (21. Merge 2 sorted lists)

3 Answers

Add your own answers!

Ask a Question