4
\$\begingroup\$

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

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
using System.Collections.Generic;
using Heap;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace LinkedListQuestions
{/// <summary>
/// https://leetcode.com/problems/merge-k-sorted-lists/
/// </summary>
    [TestClass]
    public class MergeKSortedLists
    {
        [TestMethod]
        public void LeetCodeExample()
        {
            ListNode l1 = new ListNode(1);
            l1.next = new ListNode(4);
            l1.next.next = new ListNode(5);

            ListNode l2 = new ListNode(1);
            l2.next = new ListNode(3);
            l2.next.next = new ListNode(4);

            ListNode l3 = new ListNode(2);
            l3.next = new ListNode(6);
            ListNode[] arr = new ListNode[] { l1, l2, l3 };

            ListNode res = MergeKSortedListsTest.MergeKLists(arr);

        }
    }

    public class MergeKSortedListsTest
    {
        public static ListNode MergeKLists(ListNode[] lists)
        {
            if (lists == null || lists.Length == 0)
            {
                return null;
            }

            MinHeap<ListNode> heap = new MinHeap<ListNode>(new ListNodeComparer());
            ListNode dummy = new ListNode(0);
            ListNode tail = dummy;
            foreach (ListNode node in lists)
            {
                if (node != null)
                {
                    heap.Add(node);
                }
            }

            while (heap.Count > 0)
            {
                tail.next = heap.ExtractDominating();
                tail = tail.next;
                if (tail.next != null)
                {
                    heap.Add(tail.next);
                }
            }

            return dummy.next;
        }

        public class ListNodeComparer : Comparer<ListNode>
        {
            public override int Compare(ListNode o1, ListNode o2)
            {
                if (o1.val < o2.val)
                    return -1;
                else if (o1.val == o2.val)
                    return 0;
                else
                    return 1;
            }
        }
    }
}

you do not need to review the MinHeap code!

 public abstract class Heap<T> : IEnumerable<T>
    {
        //capacity of the Queue
        private const int InitialCapacity = 0;

        private int _capacity = InitialCapacity;

        //items in the queue
        private T[] _heap = new T[InitialCapacity];

        //last item in the queue
        private int _tail = 0;

        //when growing the queue you multiply by Growfactor
        private const int GrowFactor = 2;
        // if the min size is 0 you grow the queue size by at least Min grow
        private const int MinGrow = 1;

        //how to compare the keys
        protected Comparer<T> Comparer { get; private set; }

        //store how many Items are in the queue
        public int Count { get { return _tail; } }

        //shows the current capacity of the queue
        public int Capacity { get { return _capacity; } }

        //this function is used in BubbleUp and in GetDominating
        protected abstract bool Dominates(T x, T y);

        protected Heap() : this(Comparer<T>.Default)
        {
        }
        protected Heap(Comparer<T> comparer) : this(Enumerable.Empty<T>(), comparer)
        {
        }
        protected Heap(IEnumerable<T> collection) : this(collection, Comparer<T>.Default)
        {
        }

        protected Heap(IEnumerable<T> collection, Comparer<T> comparer)
        {
            if (collection == null)
            {
                throw new ArgumentNullException("collection");
            }

            if (comparer == null)
            {
                throw new ArgumentNullException("comparer");
            }

            Comparer = comparer;
            foreach (var item in collection)
            {
                if (Count > Capacity)
                {
                    Grow();
                }

                _heap[_tail++] = item;
            }

            for (int i = 0; i < Parent(_tail - 1); i++)
            {
                BubbleDown(i);
            }
        }


        public void Add(T item)
        {
            if (Count == Capacity)
            {
                Grow();
            }

            _heap[_tail++] = item;
            BubbleUp(_tail - 1);
        }


        //when adding a new item we bubble the item from tail-1 up to its'
        //correct position
        private void BubbleUp(int i)
        {
            if (i == 0 || Dominates(_heap[Parent(i)], _heap[i]))
            {
                return; //correct domination (or root)
            }

            Swap(i, Parent(i));
            BubbleUp(Parent(i));
        }

        // when adding new items into the queue from the CTOR
        // we bubble them down
        private void BubbleDown(int i)
        {
            int dominatingNode = Dominating(i);
            if (dominatingNode == i)
            {
                return;
            }
            Swap(i,dominatingNode);
            BubbleDown(dominatingNode);
        }

        public T GetMin()
        {
            if (Count == 0)
            {
                throw new InvalidOperationException("Heap is empty");
            }
            return _heap[0];
        }

        private void Swap(int i, int j)
        {
            T tmp = _heap[i];
            _heap[i] = _heap[j];
            _heap[j] = tmp;
        }

        public static int Parent(int i)
        {
            return (i + 1) / 2 - 1;
        }

        private void Grow()
        {
            int newCapcity = _capacity * GrowFactor + MinGrow;
            var newHeap = new T[newCapcity];
            Array.Copy(_heap, newHeap, _capacity);
            _heap = newHeap;
            _capacity = newCapcity;
        }

        //return from 0 up to Count
        public IEnumerator<T> GetEnumerator()
        {
            return _heap.Take(Count).GetEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }


        //when we bubble down, when building the queue from a list in the CTOR
        // we need to understand who is dominating i, and we swap them,
        // and call bubbleDown again
        private int Dominating(int i)
        {
            int dominatingNode = i;
            dominatingNode = GetDominating(YoungChild(i), dominatingNode);
            dominatingNode = GetDominating(OldChild(i), dominatingNode);
            return dominatingNode;
        }

        private int GetDominating(int newNode, int dominatingNode)
        {
            if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode]))
            {
                return newNode;
            }
            else
            {
                return dominatingNode;
            }
        }

        private static int YoungChild(int i)
        {
            return 2 * (i + 1) - 1;
        }

        private static int OldChild(int i)
        {
            return YoungChild(i) + 1;
        }

        public T ExtractDominating()
        {
            if (Count == 0) throw new InvalidOperationException("Heap is empty");
            T ret = _heap[0];
            _tail--;
            Swap(_tail, 0);
            BubbleDown(0);
            return ret;
        }

    }

    public class MinHeap<T> : Heap<T>
    {
        public MinHeap()
            : this(Comparer<T>.Default)
        {
        }

        public MinHeap(Comparer<T> comparer)
            : base(comparer)
        {
        }

        public MinHeap(IEnumerable<T> collection) : base(collection)
        {
        }

        public MinHeap(IEnumerable<T> collection, Comparer<T> comparer)
            : base(collection, comparer)
        {
        }

        protected override bool Dominates(T x, T y)
        {
            return Comparer.Compare(x, y) <= 0;
        }
    }
\$\endgroup\$
3
\$\begingroup\$

One thing I don't like is, that you merge "in place" - that is: the input linked lists change as a side effect. I would expect them to be untouched by the method. Consider to make a new linked list as the result.


As a micro optimization you could probably spare a couple of ticks, if the input lists contain a lot of duplicate values, by iterate to the first node with a greater value in the second loop:

  while (heap.Count > 0)
  {
    ListNode node = heap.ExtractDominating();
    tail.next = node;

    while (node.next != null && node.val == node.next.val)
    {
      node = node.next;
    }

    if (node.next != null)
    {
      heap.Add(node.next);
    }
      tail = node;

  }
\$\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.