CareerCup

Consider two list as list1 and list2.
list1 = Sort(list1)
list2 = Sort(list2)
return Merge(list1,list2)

I am inserting the list in sorted order
heres 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...

1. Append list 2 to the end of list 1.
2. Now you have one in unsorted link list.
3. Use bubble sort or merge sort to sort the list.
4. Bubble sort will give you time complexity of o(n2). Merge sort has better time complexity of o(nlogn).

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() {
	}
}

Take a binary search tree implementation put all the elements from the two list in BST and trace back the BST in inorder traversal and put the element in new linked list...that elemets are automatically sorted...

Take a binary search tree implementation put all the elements from the two list in BST and trace back the BST in inorder traversal and put the element in new linked list...that elemets are automatically sorted...

This shouts heap sort.
1. Create a heap using an array - O(n)
2. Heap sort - O(nlogn)
3. Create a linked list from the array O(n)

Time complexity = O(nlogn), Space complexity = O(n)

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)

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,