com.sl.algorithms.core.list.merge

Class LinkedListMergeDnQ<T extends java.lang.Comparable>

java.lang.Object

com.sl.algorithms.core.list.merge.LinkedListMergeDnQ<T>

All Implemented Interfaces:

BaseInterface<T>, Constants, MergeEngine<T>

public class LinkedListMergeDnQ<T extends java.lang.Comparable>
extends java.lang.Object
implements MergeEngine<T>

Field Summary

Fields inherited from interface com.sl.algorithms.core.interfaces.base.Constants

ARRAY_IS_EMPTY, DATA_TYPE_NOT_SUPPORTED_YET, DECIMAL_RADIX, DELIMITER_COMMA, ELEMENT_NOT_FOUND, LIST_IS_EMPTY, OPERATION_NOT_SUPPORTED_YET

Constructor Summary

Constructors

Constructor and Description
LinkedListMergeDnQ()

Method Summary

Modifier and Type	Method and Description
ListNode<T>	merge2SortedLists(ListNode<T> list1, ListNode<T> list2) O(n+m) time and space recursive method to merge 2 sorted lists.
ListNode<T>	mergeKSortedLists(ListNode<T>[] sortedListsArray) Merge K sorted lists, using divide-n-conquer technique Complexity: - Time: O(N * logK): N = total number of nodes and K = total number of lists.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface com.sl.algorithms.core.interfaces.base.BaseInterface

checkArray, checkIntArray, checkList

Constructor Detail

LinkedListMergeDnQ

public LinkedListMergeDnQ()

Method Detail

mergeKSortedLists

public ListNode<T> mergeKSortedLists(ListNode<T>[] sortedListsArray)

Merge K sorted lists, using divide-n-conquer technique

Complexity:
- Time: O(N * logK): N = total number of nodes and K = total number of lists.
- Space: O(N): because we're using the recursive @merge2SortedLists(ListNode, ListNode) method.

Specified by:

mergeKSortedLists in interface MergeEngine<T extends java.lang.Comparable>

merge2SortedLists

public ListNode<T> merge2SortedLists(ListNode<T> list1,
                                     ListNode<T> list2)

O(n+m) time and space recursive method to merge 2 sorted lists.

Specified by:

merge2SortedLists in interface MergeEngine<T extends java.lang.Comparable>