## Interview Question

Software Engineer / Developers- 0of 0 votes
merge two unsorted linked-list into one new sorted linked list, off course in a efficient way

**Country:**United States

Bubble sort isn't even worth mentioning, unless the list is very small; It's an archaic algorithm and almost every other other algorithm performs better. Since the list is a linked list, you don't get the benefits of locality. If the list is close to being sorted, use Insertion sort. Otherwise, for a large list, use an "external sorting" algorithm, e.g. mergesort.

void MergeUnSortedList(stIntList* pList1,stIntList* pList2,stIntList*& pSorted)

{

stIntList* pList1Temp = pList1;

stIntList* pList2Temp = pList2;

std::map<int,int> mapNoVsCount;

while(pList1Temp != NULL || pList2Temp != NULL)

{

if(pList1Temp != NULL)

{

std::map<int,int>::iterator it1 = mapNoVsCount.find(pList1Temp->data);

if(it1 != mapNoVsCount.end())

it1->second++;

else

{

std::pair<int,int> key(pList1Temp->data,1);

mapNoVsCount.insert(key);

}

pList1Temp = pList1Temp->pNList;

}

if(pList2Temp != NULL)

{

std::map<int,int>::iterator it1 = mapNoVsCount.find(pList2Temp->data);

if(it1 != mapNoVsCount.end())

it1->second++;

else

{

std::pair<int,int> key(pList2Temp->data,1);

mapNoVsCount.insert(key);

}

pList2Temp = pList2Temp->pNList;

}

}

stIntList* pMerge = NULL;

std::map<int,int>::iterator begin = mapNoVsCount.begin();

while(begin != mapNoVsCount.end())

{

for(int i = 0; i < begin->second; i++)

{

insertIntIntoList(pSorted,pMerge,begin->first);

}

begin++;

}

}

My attempt:

```
public class MergeAndSort {
public static void main(String[] args) {
Node n11 = new Node(5);
Node n12 = new Node(11);
Node n13 = new Node(9);
Node n14 = new Node(11);
Node n15 = new Node(10);
n11.next = n12;
n12.next = n13;
n13.next = n14;
n14.next = n15;
Node n21 = new Node(3);
Node n22 = new Node(19);
Node n23 = new Node(12);
Node n24 = new Node(4);
Node n25 = new Node(6);
Node n26 = new Node(11);
Node n27 = new Node(4);
n21.next = n22;
n22.next = n23;
n23.next = n24;
n24.next = n25;
n25.next = n26;
n26.next = n27;
Node temp = null;
Node current = null;
Node head = temp = n11;
int count = 0;
while (temp != null) {
current = temp;
temp = temp.next;
count++;
}
temp = current.next = n21;
while (temp != null) {
temp = temp.next;
count++;
}
temp = head;
while (temp != null) {
System.out.print(temp.value + " ");
temp = temp.next;
}
System.out.println();
System.out.println("Count : " + count);
Node finalHead = mergeSort(head);
temp = finalHead;
while (temp != null) {
System.out.print(temp.value + " ");
temp = temp.next;
}
temp = current = finalHead;
while (temp != null && temp.next != null) {
boolean considered = false;
while (temp.value == temp.next.value) {
temp = temp.next;
considered = true;
}
if (considered) {
current.next = temp;
}
current = temp;
temp = temp.next;
}
System.out.println();
temp = finalHead;
while (temp != null) {
System.out.print(temp.value + " ");
temp = temp.next;
}
}
public static Node mergeSort(Node headOriginal) {
if (headOriginal == null || headOriginal.next == null)
return headOriginal;
Node a = headOriginal;
Node b = headOriginal.next;
while ((b != null) && (b.next != null)) {
headOriginal = headOriginal.next;
b = (b.next).next;
}
b = headOriginal.next;
headOriginal.next = null;
return merge(mergeSort(a), mergeSort(b));
}
public static Node merge(Node a, Node b) {
Node temp = new Node();
Node head = temp;
Node c = head;
while ((a != null) && (b != null)) {
if (a.value <= b.value) {
c.next = a;
c = a;
a = a.next;
} else {
c.next = b;
c = b;
b = b.next;
}
}
c.next = (a == null) ? b : a;
return head.next;
}
}
public class Node {
int value;
Node next;
public Node(int value) {
this.value = value;
}
public Node() {
}
}
```

Use merge sort to sort the two lists individually and then merge the lists similar to used for merge sort.

Time - O(nlgn) - n is number of total elements.

Space - O(1)

Space is O(1) as no extra space is required to merge the two sorted lists.

Remove the elements from the original list and add them to the sorted list.

E.g. 1-3-5 and 2-4 can be merged by moving 1 to the head of new list (3-5, 2-4) remain. Then add 2 making the sorted list 1-2 (3-5,4) remain and so on.

No extra space was required and hence is O(1) in space.

It's simply a merge_sort algorithm on link-list, I don't suggests to merge the list initially. It will just increase the traversing of break_list algorithm eventually you've to break the list into two.

So here it what should be done.

- 1. Perform MergeSort on List1. (mlogm) assuming size of list m.

- 2. Perform MergeSort on List2. (nlogn) assuming size of list n.

- 3. Merge two sorted List O(m+n).

MergeSort on Link-List can be performed as follows:

- 1. If size of list is one no need to sort.

- 2. break the list into two (say left, right).

- 3. recursively sort the left & right sub-lists.

- 4. merge the two sub-lists into sorted one.

Here is the sample code in C/C++

```
class Node {
public:
int value;
Node* next;
Node(int v, Node* n) : value(v), next(n) {}
};
Node* merge(Node* left, Node* right) {
Node* head = NULL, *tail = NULL;
while (left != NULL && right != NULL) {
if (left->value < right->value) {
Node* t = left->next;
if (head == NULL) {
head = tail = left;
}
else {
tail->next = left;
tail = tail->next;
}
left = t;
}
else {
Node* t = right->next;
if (head == NULL) {
head = tail = right;
}
else {
tail->next = right;
tail = tail->next;
}
right = t;
}
}
if (left != NULL) {
if (head == NULL) {
head = tail = left;
}
else {
tail->next = left;
}
}
if (right != NULL) {
if (head == NULL) {
head = tail = right;
}
else {
tail->next = right;
}
}
return head;
}
void break_list(Node* head, Node*& left, Node*& right) {
if (head == NULL)
return;
Node* slow = head, *fast = head;
Node* tailSlow = NULL;
while (fast) {
tailSlow = slow;
slow = slow->next;
fast = (fast->next) ? fast->next->next: NULL;
}
tailSlow->next = NULL;
left = head;
right = slow;
}
void printList(Node* h) {
while (h) {
cout << h->value;
h = h->next;
}
cout << endl;
}
Node* merge_sort(Node* head) {
printList(head);
// if the list has only one element, it's already sorted.
if (head == NULL || head->next == NULL)
return head;
Node* left = NULL, *right = NULL;
break_list(head, left, right);
Node* l = merge_sort(left);
Node* r = merge_sort(right);
head = merge(l, r);
printList(head);
return head;
}
Node* merge_two_lists(Node* head, Node* head2) {
Node* h = merge_sort(head);
printList(h);
Node* h2 = merge_sort(head2);
printList(h2);
Node* r = merge(h, h2);
printList(r);
return r;
}
```

the more efficient solution would be:

1. Have two pointers, P1 pointing to List 1 head, P2 pointing to List 2 head

2. Compare pointers P1 and P2 and select and add the smallest to the resultant list L3

Note: Addition is another loop, where you basically place the node in a sorted order in List 3.

This is again O(n2), but a more small and neat code,

I am inserting the list in sorted order

- Suvi February 16, 2013heres the code

if (head == null)

{

Node additem = new Node();

additem.data = item;

head = additem;

}

else

{

Node curr = head;

Node Prev = head;

if (item < head.data)

{

Node additem = new Node();

additem.data = item;

head = additem;

additem.next = curr;

}

else

{

while (curr != null)

{

if (curr.data > item)

{

Node additem = new Node();

additem.data = item;

Prev.next = additem;

additem.next = curr;

return;

}

else

{

Prev = curr;

curr = curr.next;

}

}

Node additem1 = new Node();

additem1.data = item;

Prev.next = additem1;

}

}

Now Merging the two sorted list. changing the Ist list by appending the node of the second list if its coming in between the nodes of the Ist list...Merging in assending order..

code is...

Node prev = list1.head;

curr1 = prev.next;

curr2 = list2.head;

Node tempptr = new Node();

while (curr1!=null && curr2!=null)

{

if (prev.data == curr2.data)

{

tempptr = curr2.next;

curr2.next = curr1;

prev.next = curr2;

prev = curr2;

curr2 = tempptr;

}

if (prev.data<curr2.data && curr2.data<curr1.data)

{

tempptr = curr2.next;

curr2.next = curr1;

prev.next = curr2;

prev = curr2;

curr2 = tempptr;

}

else

{

prev = curr1;

curr1 = curr1.next;

}

}

Reply to me if its not working in any condition...