CareerCup

Write a function to maere tow sorted linded list

You already have one sorted linked list A, so just add each node of the 2nd linked list(B) into its proper place. Here's a typical alg to do this...

You have the heads/tails, use those as indicators. For example, choose node 1 from A. If node 1A is greater than node 1B and less than tailB, then place it in the proper position. If node1A is not in this range, it must be greater than tailB, so append it to tailB. Do this until A is empty.

Oops. Meant place nodes from A into B.

Hi, Jack, your algorithm will have to scan linked list B for every element in A. The runing time 'd be O( n * m). We need only O(n+m). Just keep one anchor pointer for A , another for B. Move the node with smaller value to linked list C and ajust the anchor pointer. It takes O(n+m) and no additional space.

Missing: check of the list orders
if opppsite order (small to large and large to small) reverse one of the lists

Use the merge sort principle for merging two sorted linked lists.

I liked this one

16struct jsw_node *jsw_merge ( struct jsw_node *a, struct jsw_node *b )
17...{
18 struct jsw_node result, *it = &result;
19 struct jsw_node **half;
20
21 while ( a != NULL && b != NULL ) ...{
22 half = ( a->data < b->data ) ? &a : &b;
23 it->next = *half;
24 it = *half;
25 *half = (*half)->next;
26 }
27
28 it->next = ( a == NULL ) ? b : a;
29
30 return result.next;
31}

see at httpdot//wwwdoteternallyconfuzzleddotcom/tuts/algorithms/jsw_tut_sortingdotaspx

Here is the code for merging two sorted Link list without using any additional memory..

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

void merge(node * , node *);
void main()
{
	int i, n1=0,n2=0,val = 0;
	node *temp, *l1, *l2, *prev;
	printf("Enter the no. of nodes in the first link list\n");
	scanf("%d", &n1);
	printf("Enter the values of the link list in order\n");
	scanf("%d", &val);
	l1 = (node *) malloc(sizeof(node));
	l1->value = val;
	l1->next = NULL;
	prev= l1;
	for(i=1;i<n1;i++)
	{
		scanf("%d", &val);
		temp = (node *) malloc(sizeof(node));
		temp->value = val;
		temp->next = NULL;
		prev->next = temp;
		prev = temp;		
	}

	printf("Enter the no. of nodes in the second link list\n");
	scanf("%d", &n2);
	printf("Enter the values of the link list in order\n");
	scanf("%d", &val);
	l2 = (node *) malloc(sizeof(node));
	l2->value = val;
	l2->next = NULL;
	prev = l2;
	for(i=1;i<n2;i++)
	{
		scanf("%d", &val);
		node * temp = (node *) malloc(sizeof(node));
		temp->value = val;		
		temp->next = NULL;
		prev->next = temp;
		prev = temp;
	}
	merge(l1,l2);
}
void merge(node * l1, node * l2)
{
	int i;
	node * head;
	node * prev, * temp;
	if(l1 == 0 || l2 == 0)
		return;
	if(l1->value < l2->value)
	{
		head = l1;
		l1 = l1->next;
	}
	else
	{
		head=l2;
		l2 = l2->next;
	}
	prev = head;

	while(l1 != NULL && l2 != NULL)
	{
		if(l1->value < l2->value)
		{
			prev->next = l1;
			prev = l1;
			l1 = l1->next;
		}
		else
		{
			prev->next = l2;
			prev = l2;
			l2 = l2->next;
		}			
	}//End of while
	if(l1==NULL)
		prev->next = l2;
	else
		prev->next = l1;

	printf("The new sorted link list is:\n");
	temp = head;
	while(temp != NULL)
	{
		printf("%d ",temp->value);
		temp = temp->next;
	}
}