Leetcode: Merging 2 sorted lists

Question

https://leetcode.com/problems/merge-two-sorted-lists/

Merge two sorted linked lists and return it as a new 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

using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace SortingQuestions
{
    [TestClass]
    public class Merge2SortedLists
    {
        [TestMethod]
        public void TwoListsMerge()
        {
            ListNode l1 = new ListNode(1);
            l1.next = new ListNode(2);
            l1.next.next = new ListNode(4);
            ListNode l2 = new ListNode(1);
            l2.next = new ListNode(3);
            l2.next.next = new ListNode(4);
            var res = MergeTwoLists(l1, l2);
            Assert.AreEqual(1, res.val);
            Assert.AreEqual(1, res.next.val);
            Assert.AreEqual(2, res.next.next.val);
            Assert.AreEqual(3, res.next.next.next.val);
            Assert.AreEqual(4, res.next.next.next.next.val);
            Assert.AreEqual(4, res.next.next.next.next.next.val);
        }
        [TestMethod]
        public void OneEmptyList()
        {
            ListNode l1 = new ListNode(1);
            l1.next = new ListNode(2);
            l1.next.next = new ListNode(4);
            ListNode l2 = null;
            var res = MergeTwoLists(l1, l2);
            Assert.AreEqual(1, res.val);
            Assert.AreEqual(2, res.next.val);
            Assert.AreEqual(4, res.next.next.val);
        }


        public ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            ListNode result = new ListNode(0);
            if (l1 == null && l2 == null)
            {
                return null;
            }

            ListNode currRes = result;
            while (l1 != null && l2 != null)
            {
                if (l1.val < l2.val)
                {
                    currRes.next = l1;
                    l1 = l1.next;
                    currRes = currRes.next;
                }
                else
                {
                    currRes.next = l2;
                    l2 = l2.next;
                    currRes = currRes.next;
                }    
            }
            if (l1 != null)
            {
                currRes.next = l1; //concat all the rest
            }
            else
            {
                currRes.next = l2;
            }
            return result.next; // we don't pass the first value
        }
    }

    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }
}

if you could please review this code from testing point of view, in an interview. what edge cases would you expected to be tested here. please remember this is about 30 minutes. also please comment on style.

Answer 1

Style wise, the assignment currRes = currRes.next; happens no matter what, so lift it out of if-else clause:

            if (l1.val < l2.val)
            {
                currRes.next = l1;
                l1 = l1.next;
            }
            else
            {
                currRes.next = l2;
                l2 = l2.next;
            }    
            currRes = currRes.next;

Correctness wise, the condition if (l1.val < l2.val) loses the stability: if the elements compare equal, the one from l2 is merged first. Consider if (l1.val <= l2.val) (or even if (l2.val < l2.val)) instead. It is not required by the problem statement, and it doesn't matter for ints. In real life however the stability is of utmost importance, and as an interviewer I'd definitely mark it.

On the bright side, a dummy head for the merged list is a right way to go.

Answer 2

This condition is unnecessary, and can be safely deleted:

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

The problem description says, with emphasis mine:

Merge two sorted linked lists and return it as a new list.

The solution doesn't really do that, it reuses and even modifies the nodes in the input lists. The solution is accepted by the judge anyway, so I think it's a bug in the description. Just for the record.