Combining two linked lists

Question

0.00/5 (No votes)

See more:

I need help to merge and sort 2 link lists

mergeLists() is the function i try to complete

And my full code is below

C++

#include <stdio.h>

typedef struct Node
{
	int element;
	struct Node* next;	
} Node;

Node* mergeLists(Node* list1, Node* list2)
{
}

Node *createList(int x)
{
	Node *tmp;
	tmp =(Node *)malloc(sizeof(Node));
	tmp->element = x;
	tmp->next = NULL;
	return tmp;
}
Node* insertOrdered(Node *head, int x)
{
	Node *tmp;
	
	tmp = head;
	if (head->element > x) // insert at beginning
	{
		tmp = (Node *)malloc(sizeof(Node));
		tmp->element = x;
		tmp->next = head;
		return tmp;
	}
	
	while (tmp->next!=NULL && tmp->next->element <= x)
		tmp = tmp->next;
	if (tmp->next == NULL) // insert at the end 
	{
		tmp->next = (Node *)malloc(sizeof(Node));
		tmp->next->element = x;
		tmp->next->next = NULL;
	}
	else // insert in the middle 
	{
		Node *tmp2 = tmp->next;
		tmp->next = (Node *)malloc(sizeof(Node));
		tmp->next->element = x;
		tmp->next->next = tmp2;
	}
	return head;
}
void printList(Node *head)
{
	Node *tmp;
	tmp = head;
	while (tmp!=NULL)
	{
		printf("%d ",tmp->element);
		tmp = tmp->next;
	}
	printf("\n");
}
int main()
{
	Node *listA;
	Node *listB;
	Node *merged;
	listA = createList(6);
	listB = createList(4);
	
	listA = insertOrdered(listA,3);
	listA = insertOrdered(listA,9);
	listA = insertOrdered(listA,5);
	listA = insertOrdered(listA,10);
	listA = insertOrdered(listA,2);
	listB = insertOrdered(listB,1);
	listB = insertOrdered(listB,8);
	listB = insertOrdered(listB,7);
	listB = insertOrdered(listB,14);
	listB = insertOrdered(listB,11);
	listB = insertOrdered(listB,19);
	listB = insertOrdered(listB,15);

	printList(listA);	
	printList(listB);	
 	merged = mergeLists(listA,listB);
	printList(merged);	
}

Thanks.

Posted 23-Nov-11 0:38am

emrea

Updated 23-Nov-11 1:28am

LanFanNinja

v6

Add a Solution

Comments

LanFanNinja 23-Nov-11 7:29am

Edit: Fixed formating. I cannot believe it was edited 5 times before me and still no formatting!

Resmi Anna 23-Nov-11 7:37am

I tired for the same all the 5 times..but no way:(

LanFanNinja 23-Nov-11 7:58am

The "Treat my content as plain text" checkbox was checked and also I had to cut and paste it again and format as html.

LanFanNinja 23-Nov-11 8:04am

Check my solution.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

LanFanNinja · Answer 1 · 2011-11-23T02:03:00

Well I will give some code because (A) I just woke up and this code is just a quick attempt. And (B) I believe the best way to learn programming is to study others source code. But please don't just use the code try to understand what it is doing cause that is what will make you a programmer not just pasting others code ok. :)

C++

Node* mergeLists(Node* list1, Node* list2)
{
	Node *merged = createList(10);

	while(list1 != 0 || list2 != 0)
	{
		if (list1 != 0) 
		{
			merged = insertOrdered(merged, list1->element);
			list1 = list1->next;
		}
		if (list2 != 0) {
			merged = insertOrdered(merged, list2->element);
			list2 = list2->next;
		}
	}
 
    return merged;
}

also I added these to the start of the code because I was getting error C3861: 'createList': identifier not found.

C++

void printList(Node *head);
Node* insertOrdered(Node *head, int x);
Node *createList(int x);
Node* mergeLists(Node* list1, Node* list2);

Andrew Brock · Answer 2 · 2011-11-23T01:53:00

Since this looks like an assignment, I wont give real code, but what you need to do is this:

//Get an iterator of the list and create a new list
Node i1 := list1.head()
Node i2 := list2.head()
Node merge:= new list
While not i1.empty() and not i2.empty()
	//Keep adding from i1 until we reach an element in i2 which is smaller
	While i1 <= i2
		merge.add_at_tail(i1)
		i1 = i1.next()
	End While
	//Now keep adding from i2 until we reach an element in i1 which is smaller
	While i1 >= i2
		merge.add_at_tail(i2)
		i2 = i2.next()
	End While
End While
Return merge

You also need to check if you are at the end of the list before you do the comparisons

Combining two linked lists

2 solutions

Solution 2

Solution 1

Add your solution here

Preview 0