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}
 */

var mergeTwoLists = function(l1, l2, l3) {
    if (l2 === null) {
        l3.next = l1;
        return l3;
    }
    if (l1 === null) {
        l3.next = l2;
        return l3;
    }
    if (l2.val < l1.val) {
        if (l3) {
            l3.next = new ListNode(l2.val) 
        }
        else {
            l3 = new ListNode(l2.val)
        }
        return mergeTwoLists(l1, l2.next, l3)
    } else {
        if (l3) {
            l3.next = new ListNode(l1.val);
        }
        else {
            l3 = new ListNode(l1.val);
        }
        return mergeTwoLists(l1.next, l2, l3)
    }
};

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

what is ListNode - without that, the answer is a pineapple — Jaromanda X
– Jaromanda X, Commented Sep 2, 2020 at 2:01
Have you posted all code here?I think the code block above is recursion part of solution. — spike 王建
– spike 王建, Commented Sep 2, 2020 at 2:08
@Spikie yes. I am using default parameter for l3 so do not need helper function for recursive part. — Kushh
– Kushh, Commented Sep 2, 2020 at 2:11

trincot · Accepted Answer · 2020-09-02 10:42:49Z

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)
}

var mergeTwoLists = function(l1, l2) { // Only 2 parameters
    if (l2 === null) return l1; // don't prepend anything
    if (l1 === null) return l2; // don't prepend anything
    let node;
    if (l2.val < l1.val) {
        node = new ListNode(l2.val);
        node.next = mergeTwoLists(l1, l2.next);
    } else {
        node = new ListNode(l1.val);
        node.next = mergeTwoLists(l1.next, l2);
    }
    return node;
};

// 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));

Thx for the great explanation. I guess my conception of recursion with linked lists was incorrect

Emma Marcier · Accepted Answer · 2020-09-02 02:17:15Z

0

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
    }
}

edited Sep 2, 2020 at 2:17

answered Sep 2, 2020 at 2:09

Emma Marcier

27.8k12 gold badges49 silver badges71 bronze badges

2 Comments

Kushh Over a year ago

This makes sense. Can you pinpoint where I am going wrong though in my logic or understanding of linked lists? I am also trying to conditionally update the next node to either l1 or l2's depending on which is smaller and updating all nodes in the recursive function. One thing I tried is making it l3.next.next when updating it inside the conditional blocks but then it failed because it said I cant update the null property

spike 王建 Over a year ago

I think @Kushh need a reason why his solution not worked,but not an answer for the leetcode

kapil pandey · Accepted Answer · 2020-09-02 03:12:57Z

0

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))

edited Sep 2, 2020 at 3:12

answered Sep 2, 2020 at 2:20

kapil pandey

1,9231 gold badge16 silver badges26 bronze badges

1 Comment

trincot Over a year ago

This becomes quite slow when the input lists are long. The problem is that each time a recursive call is made, the l3 list has to be iterated from its front to its end. As this list becomes longer and longer, that work becomes longer as well, leading to a quadratic time complexity.

Collectives™ on Stack Overflow

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

3 Answers 3

1 Comment

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related