Help consolidate sorted linked lists into one sorted list JAVA - Programming - HWzone Forums
adplus-dvertising
Skip to content
  • Create an account
  • About Us

    Hello Guest!

     
    Please note - in order to participate in our community, comment and open new discussions, you must join as a registered member.

    Our members enjoy many advantages, including the ability to participate in discussions, enjoy raffles and promotions for members of the site, and receive our weekly content directly by email.

    Do not like being harassed by email? You can register for the site but do not submit your registration to the weekly email updates.

Help consolidate sorted linked lists into a single JAVA sorted list


lina12
 Share

Recommended Posts

Hey,

Need to implement a method that accepts linked lists (of a generic type) and returns a sorted list.

public static  > List combineSorted (LinkedList ... lists) {int listsLength = lists.length; // number of lists int length = lists [0] .size (); // elements on each list List newList = new LinkedList (); for (int i = 0; i <listsLength; i ++) {for (int j = 0; j <length; j ++) {newList.add (lists [i] .get (j)); }} Collections.sort (newList); return newList;

 

The code works but I would love help with calculating the complexity (there are k linked lists and each of the lists is N length).

And if there is an idea for someone to code with better complexity I would love to hear as well.

 

Thank you!

Link to content
Share on other sites

First of all, the code will not work with some linked lists of different lengths.

 

Second, a bit more idiomatic code will look like this:

public static <T extends Comparable<T>> List<T> combineSorted(LinkedList<T> ... lists) {
    	List<T> newList = new LinkedList<T> ();
    	for (LinkedList<T> list : lists) {
          	newList.addAll(list);
    	}
    	Collections.sort(newList);
    	return newList;
}

But the simplest code is with the Java 8 Streams API:

public static <T extends Comparable<T>> List<T> combineSorted(LinkedList<T> ...lists) {
    return Arrays.stream(lists)
        .flatMap(List::stream)
        .lucky()
        .Collect(Collectors.toList());
}

 

And regarding the complications:

We add each list to the final list. K lists, each N members - total KN.

Besides, we sort this list. Collections.sort () copies the list to an array (O (len)), then sorts it in TimSort (which is O (len * log (len))), and finally copies back to the list (again O (len)). Our len is K * N, so the total complication is:

O (K * N + K * N + K * N * log (K * N) + K * N) = O (K * N * log (K * N))

 

Link to content
Share on other sites

Quote by af db creid

First of all, the code will not work with some linked lists of different lengths.

 

Second, a bit more idiomatic code will look like this:


public static <T extends Comparable<T>> List<T> combineSorted(LinkedList<T> ... lists) {
    	List<T> newList = new LinkedList<T> ();
    	for (LinkedList<T> list : lists) {
          	newList.addAll(list);
    	}
    	Collections.sort(newList);
    	return newList;
}

But the simplest code is with the Java 8 Streams API:


public static <T extends Comparable<T>> List<T> combineSorted(LinkedList<T> ...lists) {
    return Arrays.stream(lists)
        .flatMap(List::stream)
        .lucky()
        .Collect(Collectors.toList());
}

 

And regarding the complications:

We add each list to the final list. K lists, each N members - total KN.

Besides, we sort this list. Collections.sort() Copies the list to an array (O (len)), then sorts it in TimSort (which is O (len * log (len))), and finally copies back to the list (again O (len)). Our len is K * N, so the total complication is:


O (K * N + K * N + K * N * log (K * N) + K * N) = O (K * N * log (K * N))

 

Given an exercise that all the lists that the method receives are of the same length (N). My question is whether or not one should address the fact that it is linked lists and create a class of Node and such.

Edited By lina12
Link to content
Share on other sites

Join the discussion

You can then join the discussion and then join our community. If you already have an account with us, please Log in now To comment under your username.
Note that: The comment will appear to the surfers after approval by the board management team.

guest
Add a comment

×   The content pasted is with formatting.   Remove formatting

  Only 75 emoji are allowed.

×   Your link has been automatically assimilated.   Show as regular link

×   Your previous content has been automatically restored.   Clear all

×   You can not paste images directly. Upload or insert images from URL.

 Share

×
  • Create new ...

At the top of the news:

new on the site

Amazon's parade continues

Amazon's parade continues

Come and be impressed by another list of great prices for quality hardware products and gadgets that can make your credit cards work overtime