CareerCup

void MergeTwoSortedList(node** list1, node** list2)
{
        node* temp = NULL;
        node* slow = NULL;
        node* fast = NULL;
        while(*list1)
        {
                if((*list1)->val <= (*list2)->val)
                {
                        temp = *list1;
                        *list1 = (*list1)->next;
                        temp->next = NULL;
                        temp->next = *list2;
                        *list2 = temp;
                }
                else
                {
                        slow = *list2;
                        fast = (*list2)->next;
                        while(fast != NULL && fast->val <= (*list1)->val)
                        {
                                slow = slow->next;
                                fast = fast->next;
                        }
                        temp = *list1;
                        *list1 = (*list1)->next;
                        temp->next = fast;
                }
        }
}

The list "list2" contains the merged list of list1 and list2.

private Node mergeTwoSortedList(Node first, Node second){
		Node mergedNode = null;
		int firstCount = count(first);
		int secondCount = count(second);
		if(firstCount >0 || secondCount > 0){
			Node mergedNodePtr = null;
			Node firstPtr = first;
			Node secondPtr = second;
			while(firstPtr !=null && secondPtr !=null ){
				if(firstPtr.getIntValue()>secondPtr.getIntValue()){
					Node tempNode = new Node();
					tempNode.setIntValue(secondPtr.getIntValue());
					if(mergedNode == null){
						mergedNode = tempNode;
						mergedNodePtr = mergedNode;
					}
					else{
						mergedNodePtr.setNext(tempNode);
						mergedNodePtr = mergedNodePtr.getNext();
					}
					secondPtr = secondPtr.getNext();
				}
				else{
					Node tempNode = new Node();
					tempNode.setIntValue(firstPtr.getIntValue());
					if(mergedNode == null){
						mergedNode = tempNode;
						mergedNodePtr = mergedNode;
					}
					else{
						mergedNodePtr.setNext(tempNode);
						mergedNodePtr = mergedNodePtr.getNext();
					}
					firstPtr = firstPtr.getNext();
				}
			 
			}
			
			if(firstPtr == null && secondPtr !=null){
				while (secondPtr != null) {
					Node tempNode = new Node();
					tempNode.setIntValue(secondPtr.getIntValue());
					if (mergedNode == null) {
						mergedNode = tempNode;
						mergedNodePtr = mergedNode;
					}
					else{
						mergedNodePtr.setNext(tempNode);
						mergedNodePtr = mergedNodePtr.getNext();
					}
					secondPtr = secondPtr.getNext();
				}
			}
			if(secondPtr == null && firstPtr !=null){
				while (firstPtr != null) {
					Node tempNode = new Node();
					tempNode.setIntValue(firstPtr.getIntValue());
					if (mergedNode == null) {
						mergedNode = tempNode;
						mergedNodePtr = mergedNode;
					}
					else{
						mergedNodePtr.setNext(tempNode);
						mergedNodePtr = mergedNodePtr.getNext();
					}
					firstPtr = firstPtr.getNext();
				}
			}
			
			
		}
		return mergedNode;
	}

private Node mergeTwoSortedList(Node first, Node second){
		Node mergedNode = null;
		int firstCount = count(first);
		int secondCount = count(second);
		if(firstCount >0 || secondCount > 0){
			Node mergedNodePtr = null;
			Node firstPtr = first;
			Node secondPtr = second;
			while(firstPtr !=null && secondPtr !=null ){
				if(firstPtr.getIntValue()>secondPtr.getIntValue()){
					Node tempNode = new Node();
					tempNode.setIntValue(secondPtr.getIntValue());
					if(mergedNode == null){
						mergedNode = tempNode;
						mergedNodePtr = mergedNode;
					}
					else{
						mergedNodePtr.setNext(tempNode);
						mergedNodePtr = mergedNodePtr.getNext();
					}
					secondPtr = secondPtr.getNext();
				}
				else{
					Node tempNode = new Node();
					tempNode.setIntValue(firstPtr.getIntValue());
					if(mergedNode == null){
						mergedNode = tempNode;
						mergedNodePtr = mergedNode;
					}
					else{
						mergedNodePtr.setNext(tempNode);
						mergedNodePtr = mergedNodePtr.getNext();
					}
					firstPtr = firstPtr.getNext();
				}
			 
			}
			
			if(firstPtr == null && secondPtr !=null){
				while (secondPtr != null) {
					Node tempNode = new Node();
					tempNode.setIntValue(secondPtr.getIntValue());
					if (mergedNode == null) {
						mergedNode = tempNode;
						mergedNodePtr = mergedNode;
					}
					else{
						mergedNodePtr.setNext(tempNode);
						mergedNodePtr = mergedNodePtr.getNext();
					}
					secondPtr = secondPtr.getNext();
				}
			}
			if(secondPtr == null && firstPtr !=null){
				while (firstPtr != null) {
					Node tempNode = new Node();
					tempNode.setIntValue(firstPtr.getIntValue());
					if (mergedNode == null) {
						mergedNode = tempNode;
						mergedNodePtr = mergedNode;
					}
					else{
						mergedNodePtr.setNext(tempNode);
						mergedNodePtr = mergedNodePtr.getNext();
					}
					firstPtr = firstPtr.getNext();
				}
			}
			
			
		}
		return mergedNode;
	}

NodePtr tmp,tmp1,tmp2;
tmp1 = ll1; tmp2 = ll2; //point to root initially
tmp = ll1;
while(tmp1!=NULL && tmp2!=NULL){
   if(*tmp2<*tmp1){
      tmp = tmp2
      tmp2 = tmp->next;
      tmp->next = tmp1;
      continue;
   }else{
      tmp = tmp1;
      tmp1 = tmp->next;
      tmp->next = tmp2;
   }
}
if(*ll2<*ll1)
   ll1 = ll2;
else
   ll2 = ll1;
//both lists should be merged and ll1 & ll2 point to the same list

node * MergeLL(node *L1, node *L2)
{
if(L1 == null)
return L2;

if(L2 == null)
return L1;

if(L1->value <= L2->value)
{
L1->next = MergeLL(L1->next, L2);
return L1;
}
L2->next = MergeLL(L1, L2->next);
return L2;
}