CareerCup

#include <iostream>

template <typename T>
struct node {
	node(T value) : value{value}, next{nullptr} {}
	~node() { if(next != nullptr) delete(next); }

	T value;
	node* next;
};

template <typename T>
node<T> * merge_list(node<T> * head1, node<T> * head2) {	
	node<T>* ptr1 = head1;
	node<T>* ptr2 = head2;

	node<T>* merged_list = nullptr;
	node<T>* out;

	while(ptr1 != nullptr && ptr2 != nullptr) {
		if(ptr1->value > ptr2->value) {
			//std::cout << ptr2->value << std::endl;

			if(merged_list == nullptr) {
				merged_list = new node<T>(ptr2->value);
				out = merged_list;
			} else {
				out->next = new node<T>(ptr2->value);
				out = out->next;
			}

			ptr2 = ptr2->next;
		} else {
			//std::cout << ptr1->value << std::endl;
			
			if(merged_list == nullptr) {
				merged_list = new node<T>(ptr1->value);
				out = merged_list;
			} else {
				out->next = new node<T>(ptr1->value);
				out = out->next;
			}

			ptr1 = ptr1->next;
		}
	}

	while(ptr1 != nullptr) {
		//std::cout << ptr1->value << std::endl;
		out->next = new node<T>(ptr1->value);
		out = out->next;

		ptr1 = ptr1->next;
	}

	while(ptr2 != nullptr) {
		//std::cout << ptr2->value << std::endl;
		out->next = new node<T>(ptr2->value);
		out = out->next;

		ptr2 = ptr2->next;
	}

	return merged_list;
}

int main() {
	node<int>* head1 = new node<int>(2);
	head1->next = new node<int>(2);
	head1->next->next = new node<int>(4);
	head1->next->next->next = new node<int>(6);

	node<int>* head2 = new node<int>(1);
	head2->next = new node<int>(3);
	head2->next->next = new node<int>(5);

	node<int>* merged_list = merge_list<int>(head1, head2);

	delete head1;
	delete head2;
	
	node<int>* ptr = merged_list;
	while(ptr != nullptr) {
		std::cout << ptr->value << std::endl;
		ptr = ptr->next;
	}

	delete merged_list;

	return 0;
}

public static Node mergeLists(Node head1, Node head2) {

	Node newHead = new Node();
	if (head1.value <= head2.value) {
	    newHead.value = head1.value;
	    head1 = head1.next;
	} else {
	    newHead.value = head2.value;
	    head2 = head2.next;
	}
	Node prev = newHead;
	while (head1 != null && head2 != null) {
	    Node n = new Node();
	    if (head1.value <= head2.value) {
		n.value = head1.value;
		head1 = head1.next;
	    } else {
		n.value = head2.value;
		head2 = head2.next;
	    }
	    prev.next = n;
	    prev = n;
	}
	while (head1 != null) {
	    Node n = new Node();
	    n.value = head1.value;
	    head1 = head1.next;
	    prev.next = n;
	    prev = n;
	}
	while (head2 != null) {
	    Node n = new Node();
	    n.value = head2.value;
	    head2 = head2.next;
	    prev.next = n;
	    prev = n;
	}
	
	return newHead;
    }

// this is C like code should be easy to adapt to Java.

SingleNode *linkedListMerge(SingleNode *list1, SingleNode *list2)
{
    SingleNode *head = nil;
    SingleNode *current = nil;
    
    while (list1 != nil || list2 != nil)
    {
        int value1 = list1 ? list1.value : INT_MAX;
        int value2 = list2 ? list2.value : INT_MAX;
        
        if (value1 < value2)
        {
            if (current != nil)
            {
                current.next = list1;
                current = list1;
            }
            else
                head = current = list1;
            
            list1 = list1.next;
        }
        else
        {
            if (current != nil)
            {
                current.next = list2;
                current = list2;
            }
            else
                head = current = list2;
            
            list2 = list2.next;
        }
    }
    
    return head;
}

C code to merge two sorted linked list. The original list is destroyed and pointers are modified so as to obtain a sorted list. Hence space complexity is O(1) and time complexity is O(n+m) when n+m are total number of nodes in both the list.

Node *mergeList(Node *i, Node *j)
{
    Node *node = i;
    Node *node1 = j;
    Node *temp,*index=NULL,*head=NULL;
    int flag=0;
    while(1){
       if(node == NULL || node1 == NULL){
	   break;
       }
       if(node->value <= node1->value){
	  if(head == NULL){
	      head = node;
	      index = node;
	      node = node->next;
	      continue;
	  }
	  index->next = node;
	  index = node;
	  node = node->next;
       }else{
	  if(head == NULL){
	     head = node1;
	     index = node1;
	     node1=node1->next;
	     continue;
	  }
	  index->next = node1;
	  index = node1;
	  node1 = node1->next;
       }
    }



   if(node!=NULL){
     index->next = node;
   }else if(node1 != NULL){
     index->next = node1;
   }

   return head;

}

By adjusting each node's pointer to next, we can have
(1)O(len1+len2) time complexity in worst case, and O(min(len1,len2)) in best
(2)O(1) space complexity

Node* merge(Node* head1, Node* head2)
{
    if(head1 == NULL) return head2;
    if(head2 == NULL) return head1;

    //determine head of the merged list
    Node* head, *p;
    if(head1->value > head2->value){
        head = head2;
        head2 = head2->next;
    }
    else{
        head = head1;
        head1 = head1->next;
    }

    //connect successors
    for(p = head; head1 && head2; ){
        if(head1->value > head2->value){
            p->next = head2;
            head2 = head2->next;
        }
        else{
            p->next = head1;
            head1 = head1->next;
        }
    }

    //connect tail
    p->next = head1 ? head1 : head2;
    
    return head;
}

#include<string>
#include<iostream>

class Node{

public: 

	int value; 
	Node* next; 
	
	Node(){
		value = 0;
		next = NULL;
	}
	Node(int v, Node* n) { 
		value = v; 
		next = n; 
	} 

	void PrintList();
};

void printList(Node* node){

	
	while(1){
		
		std::cout << node->value;

		if (node->next == NULL){
			std::cout << std::endl;
			break;
		}

		std::cout << " -> ";
		node = node->next;
	}
}

Node* mergeList(Node* head1, Node* head2){
	Node* newNode;
	
	if(head1 == NULL && head2 == NULL)
	{
		newNode = NULL;

	}else if(head1 == NULL){
		newNode = new Node(head2->value, mergeList(head1, head2->next));
	}else if(head2 == NULL){
		newNode = new Node(head1->value, mergeList(head1->next, head2));
	}else if(head1->value < head2->value){
		newNode = new Node(head1->value, mergeList(head1->next, head2));
	}else{
		newNode = new Node(head2->value, mergeList(head1, head2->next));
	}
		
	return newNode;
}

int main(){

	Node* node1 = new Node(1, new Node(2, new Node(3, new Node(4, NULL))));
	Node* node2 = new Node(1, new Node(3, new Node(5, new Node(7, NULL))));

	
	printList(mergeList(node1, node2));
}

node* mergeSortedLists(node* head, node* head2)
{
	node* temp1= head;
	node* temp2=head2;
	node* temp3;
	node* temp4;
	int i=0;

	while( temp1 != NULL && temp2 !=NULL)
	{
		if( temp1->data < temp2->data)
		{
			if( i==0)
			{
				head=temp1;
			}
			temp3=temp1->next;
			temp1->next=temp2;
			temp1=temp3;
			//temp2=temp1;

		}
		else
		{
			if( i==0)
			{
				head=temp2;
			}
			temp4=temp2->next;
			temp2->next=temp1;
			temp2=temp4;
			//temp1=temp2;
		}
		i++;

	}
	
	
 return head;



}