CareerCup

If there are no restrictions, this could be done in O(n).
Assuming the following structure:

struct _node
{
	struct _node* next;
	int data;
};

And assuming the interface of the function... This is my solution:

void merge(struct _node* h1, struct _node* h2)
{
	while (h1->next != NULL)
		h1 = h1->next;
	h1->next = h2;
}

A nice optimization would be to have another structure for the list head, saving the last element as such:

struct _head
{
	struct _node* first;
	struct _node* last;
}

Then, an O(1) solution is possible:

void merge(struct _head* h1, struct _head* h2)
{
	h1->last->next = h2;
	h1->last = h2->last
}

public class Merge {

private LinkedList<String> listOne;
private LinkedList<String> listTwo;

public Merge() {
listOne = new LinkedList<String>();
listOne.add("One");
listOne.add("Two");
listOne.add("Three");
listOne.add("Four");

listTwo = new LinkedList<String>();
listTwo.add("A");
listTwo.add("B");
listTwo.add("C");
listTwo.add("D");
listTwo.add("E");
listTwo.add("F");
listTwo.add("G");
}

private int getBiggerSize() {
int result;
int sizeListOne = listOne.size();
int sizeListTwo = listTwo.size();
if(sizeListOne < sizeListTwo) {
result = sizeListTwo;
} else {
result = sizeListOne;
}
return result;
}

public void merge() {
LinkedList<String> result = new LinkedList<String>();
int len = getBiggerSize();
for(int i=0; i<len; i++) {
if(!listOne.isEmpty()) {
result.add(listOne.element());
listOne.remove();
}
if(!listTwo.isEmpty()) {
result.add(listTwo.element());
listTwo.remove();
}
}
System.out.println("List One: "+ listOne.toString());
System.out.println("List Two: "+ listTwo.toString());
System.out.println("List Merged: "+ result.toString());
}
}

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<process.h>
typedef struct node
{
	int data;
	struct node*link;
}node;

node*create()
{
		node *start,*last,*temp;
	start=NULL;
	char choice;
	printf("enter choice:");
	fflush(stdin);
	scanf("%c",&choice);
	do
	{
		temp=(node*)malloc(sizeof(node));
		printf("enter data");
		scanf("%d",&(temp->data));
		if(temp==NULL)
		printf("not enough memory to create node");
		else
		{
			if(start==NULL)
			{
				start=temp;
				last=start;
			}
			else
			{
				last->link=temp;
				last=temp;
			}
		}
		printf("enter choice:");
		fflush(stdin);
		scanf("%c",&choice);

	
}while(choice=='y');
if(start!=NULL)
	last->link=NULL;
	return(start);
}
void print(node*start)
{
	node*temp;
	for(temp=start;temp!=NULL;temp=temp->link)
	printf("%d\t",temp->data);
}
node*convert(node*x,node*y)
{
	node*z,*temp;
	z=x;
	temp=z;
	x=x->link;
	while(x!=NULL&&y!=NULL)
	{
		temp->link=y;
		temp=y;
		y=y->link;
		temp->link=x;
		temp=x;
		x=x->link;
	}
	while(x!=NULL)
	{
		temp->link=x;
		x=NULL;
	}
	while(y!=NULL)
	{
		temp->link=y;
		y=NULL;
	}
	return z;
}
int main()
{

	node*x,*y,*z;
	printf("1st ll");
	x=create();
	printf("2nd ll");
	y=create();
	z=convert(x,y);
	print(z);

}

public static void merge2LinkedLists(LinkedList<String> list1, LinkedList<String> list2){
        int size = Math.max(list1.size(), list2.size());
        LinkedList<String> result = new LinkedList<>();
        while(size > 0) {
            if(!list1.isEmpty()){
                result.add(list1.remove());
            }
            if(!list2.isEmpty()) {
                result.add(list2.remove());
            }
            size--;
        }
        
        System.out.println(result.toString());
        
    }