CareerCup

I guess the question makes more sense if both lists are sorted and you want to merge them in sorted manner , but without creating extra space.

A : 1--> 3 --> 5
B : 2--> 4

Then output should be 1-->2 --> 3 --> 4 --> 5 but no new nodes should be created.

One Soln:
Time O(m+n), space : O(1)
algo : take pointer R and move it to current lowest node.

p = head1
q = head2
r = null;
head3 = null;

While(p && q)
{
if(p--> data < q--> data)
{
if(r== NULL)
{
head3 = p;
}
else
{
R --> next = p;
}

R = p;
R = R--> next;
}
Else
{
if(R == NULL)
{
head3 = q;
}
Else
{
R --> next = q;
}

R = q;
q = q --> next;
}
}

if(p) R--> next = p;
else if (q) R --> next = q;

Return head3;

public static LinkedListNode Merge_Two_List(LinkedListNode head1,LinkedListNode head2){
LinkedListNode current1=(head1.data<=head2.data?head1:head2);
LinkedListNode current2=(current1==head1?head2:head1);
LinkedListNode newhead=current1;
LinkedListNode pervious=current1;

while(current1!=null&&current2!=null){
if(current1.data<=current2.data){
pervious=current1;
current1=current1.next;
continue;
}
else{
LinkedListNode nextcurrent2=current2.next;
pervious.next=current2;
current2.next=current1;
pervious=current2;
current2=nextcurrent2;
}
}
if(current1==null){
pervious.next=current2;
return newhead;
}
else{
return newhead;
}

}

According to your question you can join them.
i.e next of last node of list A = start of list B.

An example will be helpful in understanding what is expected from merging. Can you please provide a coupler of them?

Yeah, it seems too easy that you can just append the list....sorted list made it more challenging.

Node* merge_linkedlists_sorted(Node* a, Node* b) {
  if (!a || !b) return NULL;
  Node* prev_a = NULL;
  Node* curr_a = a;
  Node* curr_b = b;

  while (curr_b) {
    if (curr_a && curr_a->val < curr_b->val) {
      curr_a = curr_a->next;
    }
    else {
      // insert curr_b between prev_a and curr_a
      Node* b_next = curr_b->next;
      curr_b->next = curr_a;

      // if prev_a is NULL, we need to insert in the beginning of 'a'
      if (prev_a) prev_a->next = curr_b;
      else a = curr_b; // curr_b is first element in 'a'

      // If curr_a is NULL, that means we're at the end of 'a'
      if (curr_a) {
        prev_a = curr_a;
        curr_a = curr_a->next;
      }
      curr_b = b_next; 
    }
  }
  return a;
}

.

give input as 0 to terminate the list

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int val;
	struct node *next;
};

struct node* createlist()
{
	struct node *head,*temp,*prev;
	printf("enter the values");
	int j=1;
	head=malloc(sizeof(struct node));
	scanf("%d",&head->val);
	head->next=NULL;
	j=head->val;
	prev=head;
		
	while(1)
	{
		scanf("%d",&j);
		if(j==0)
		break;
	    prev->next=malloc(sizeof(struct node));
	    temp=prev->next;
		temp->val=j;
		temp->next=NULL;
		prev->next=temp;
		prev=temp;
		
		
		}
  return head;
  
}

void display(struct node *head)
{
	while(head->next!=NULL)
	{
		
		printf("%d->",head->val);
		head=head->next;
		}
	printf("%d",head->val);
		printf("\n");
}

struct node * merge(struct node *head1,struct node *head2)
{
	struct node *head,*temp,*pre;
	if(head1->val<head2->val)
	{
	head=head1;
	head1=head1->next;
    }
	else
	{
	head=head2;
	head2=head2->next;
    }
    pre=head;
    //printf("hi");
	while(1)
	{
		//printf("one");
		if(head1!=NULL   && head2!= NULL)
		{
		if(head1->val<head2->val)
		{
			pre->next=head1;
			pre=head1;
			head1=head1->next;
			pre->next=NULL;
			
		}
		else
		{
			
			pre->next=head2;
			pre=head2;
			head2=head2->next;
			pre->next=NULL;
			
			
		}
		
	}
	
		if(head1==NULL)
		{
			
			while(head2!=NULL)
			{
				pre->next=head2;
				pre=head2;
				head2=head2->next;
				}
			pre->next=NULL;
			break;
			
		}
		if(head2==NULL)
		{
			
			while(head1!=NULL)
			{
				pre->next=head1;
				pre=head1;
				head1=head1->next;
				}
			pre->next=NULL;
			break;
			
		}
		//printf("%d  %d  %d",temp->val,head1->val,head2->val);
    }
	return head;
}
int main()
{
	struct node  *head1,*head2,*head;
	head1=createlist();
	display(head1);
	head2=createlist();
	display(head2);
	head=merge(head1,head2);
	printf("\nmerged list is\n");
	display(head);

}

I want algorithm with clarity steps