Given two linked list, insert nodes of second linked list into first at alternate position of first list.
Ex- first List is 1->2->3->4->5 and second list is 6->7->8->9->10
first list should be 1->6->2->7->3->8->4->9->5->10 and second list empty
The nodes of second list should be inserted only if positions are available.
Ex- first List is 1->2->3- and second list is 4->5->6->7->8
first list should be 1->4->2->5->3->6 and secodn list should be 7->8
Use of extra space is not allowed. Expected tiem complexity should be O(n) where n is the number of nodes.
Ex- first List is 1->2->3->4->5 and second list is 6->7->8->9->10
first list should be 1->6->2->7->3->8->4->9->5->10 and second list empty
The nodes of second list should be inserted only if positions are available.
Ex- first List is 1->2->3- and second list is 4->5->6->7->8
first list should be 1->4->2->5->3->6 and secodn list should be 7->8
Use of extra space is not allowed. Expected tiem complexity should be O(n) where n is the number of nodes.
// MergeLinkedList.cpp : Defines the entry point for the console application.
ReplyDelete//
#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
typedef struct node
{
int data;
struct node *next;
}myNode;
void push (myNode **head, int data)
{
myNode *newNode= (myNode*)malloc(sizeof(myNode));
newNode->data=data;
newNode->next=*head;
*head= newNode;
}
void printList(myNode *head)
{
while(head)
{
printf("%d ",head->data);
head=head->next;
}
}
void merge(myNode *p, myNode **q)
{
myNode *p_curr=p, *q_curr=*q;
myNode *p_next=NULL, *q_next=NULL;
while(p_curr && q_curr)
{
// save next pointers
p_next=p_curr->next;
q_next=q_curr->next;
//make next of p as q
q_curr->next=p_next;
p_curr->next=q_curr;
//update pointers
p_curr=p_next;
q_curr=q_next;
}
*q=q_curr;
}
int main()
{
myNode *head1=NULL, *head2=NULL;
int n;
push(&head1, 3);
push(&head1, 2);
push(&head1, 1);
push(&head2, 8);
push(&head2, 7);
push(&head2, 6);
push(&head2, 5);
push(&head2, 4);
printf("Lists before modification\n");
printList(head1);
printf("\n");
printList(head2);
printf("\n");
merge(head1,&head2);
printf("Lists after modification\n");
printList(head1);
printf("\n");
printList(head2);
getch();
return 0;
}