21 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.

C# Solution 1: Iterative O(n)¶

namespace Algorithms.Medium
{
  public class MergeTwoSortedLists
  {
    public ListNode Merge(ListNode l1, ListNode l2)
    {
      var sumHead = new ListNode(0);
      var currentNode = sumHead;

      while (l1 != null || l2 != null)
      {
        if (l1.val < l2.val)
        {
          currentNode.next = l1;
          l1 = l1.next;
        }
        else
        {
          currentNode.next = l2;
          l2 = l2.next;
        }

        currentNode = currentNode.next;
      }

      if (l1 != null) currentNode.next = l1;
      if (l2 != null) currentNode.next = l2;

      return sumHead.next;
    }
  }
}

Solution 2: Recursive O(n)¶

public class MergeTwoSortedLists
{
  public ListNode Merge(ListNode l1, ListNode l2)
  {
    // If one of the list is empty, return the other one.
    if (l1 == null || l2 == null) return l1 ? l1 : l2;
    // The smaller one becomes the head.
    if (l1.val < l2.val)
    {
      l1.next = Merge(l1.next, l2);
      return l1;
    }
    else
    {
      l2.next = Merge(l1, l2.next);
      return l2;
    }
  }
}