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

Example:
--------
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
*/

namespace Problems.LeetCode.LinkedList.MergeTwoSortedLists_21
{
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int x) { this.val = x; }
    }

    public class Solution
    {
        /// <summary>
        ///     Merges two sorted lists into one sorted list.
        ///     Time complexity : O(n)
        ///     Space complexity : O(1)
        /// </summary>
        /// <param name="l1">A ListNode object.</param>
        /// <param name="l2">A ListNode object.</param>
        public ListNode MergeTwoLists(ListNode l1, ListNode l2)
        {
            if (l1 == null)
                return l2;

            if (l2 == null)
                return l1;

            ListNode head = null, tail = null, current = null;

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

                if (head == null)
                {
                    head = current;
                    tail = current;
                }
                else
                {
                    tail.next = current;
                    tail = tail.next;
                }
            }

            current = (l1 == null) ? l2 : l1;

            while (current != null)
            {
                tail.next = current;
                current = current.next;
                tail = tail.next;
            }

            tail.next = null;

            return head;
        }
    }
}