CODEWITHSUNDEEP
sortingmergelinked-list
Liondancer
Liondancer

Reputation: 16469

Merging 2 unsorted linked lists to one sorted linked list

I am trying to solve a problem to efficiently merge 2 unsorted Linked Lists into one sorted Linked List. I have some ideas.

  1. Simply merge the 2 linked lists and than sort (mergesort or quicksort)
  2. Sort both individually and merge the two follow this concept.

How to merge two sorted arrays into a sorted array?

Those are about all the algorithms I can think of. Does anyone else have any better and more efficient ways to solve this problem?

Upvotes: 0

Views: 2650

Answers (3)

zookastos
zookastos

Reputation: 935

Another approach will be to use BST. Add list 1 elements into BST, then add list 2 elements in BST. Then use inorder traversal of BST and put elements into the list 3 which will be sorted.

O(nlogn)

Upvotes: 1

Gopi
Gopi

Reputation: 19864

First merge both the lists to form a single linked list and then do sort this single list.

Upvotes: 1

Peter Wooster
Peter Wooster

Reputation: 6089

You should just catenate the two lists into a single list and sort that list.

This is more straight forward than sorting them first and is less code and will take the same amount of time as the the second option.

Upvotes: 2

Related Questions