0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Are these questions you ask really interview-questions or are you doing them just for practice? What feedback did you get in your interview? \$\endgroup\$ – t3chb0t Jan 30 at 16:13
  • \$\begingroup\$ It is my friend's interview. My code is ok. He was asked to explain what he wrote just a few test cases. And told them it was a time issues. The interview we asked if knows what are unit tests and smoke tests. And why he didn't check all the edge cases. I told him that this code is great and the interviewer was wierd \$\endgroup\$ – Gilad Jan 30 at 20:13
4
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.