Merging 2 unsorted linked lists to one sorted linked list

Question

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

Simply merge the 2 linked lists and than sort (mergesort or quicksort)
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?

score 2 · Answer 1 · answered Jul 27 '14 at 01:23

2

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.

answered Jul 27 '14 at 01:23

Peter Wooster

6,009
2
27
39

Would that be O ( (n + m) (log(n + m)) ) ? – Bernie Lenz Jul 14 '18 at 23:38

score 1 · Answer 2 · answered Jul 28 '14 at 12:25

1

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

answered Jul 28 '14 at 12:25

Gopi

19,784
4
24
36

score 1 · Answer 3 · answered Oct 20 '15 at 07:09

1

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)

answered Oct 20 '15 at 07:09

zookastos

917
10
37

This would give similar performance to doing mergesort on both lists and then merging them, isn't it? – Murphy Oct 18 '16 at 04:34
ofcourse. I mentioned that it is O(nlogn). It is efficient space wise. Plus there is no rearranging of elements involved, as there is in mergesort leading to more computation. – zookastos Oct 18 '16 at 15:39

Merging 2 unsorted linked lists to one sorted linked list

3 Answers3