C++

Forum

 
Merge A Linked List...What if reach NULL ?

hentaiw (273)
Assuming 2 lists are sorted (croissant),this function will merge 2 list and put pointer to the head...Note : it doesn't create nor delete any node.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
IntNode* merge(IntNode*& head1,IntNode*& head2)
{
	IntNode* head;

	if(head1->getData() <= head2->getData())
		head = head1;
	else
		head = head2;

	IntNode* next1 = head1->getLink();
	IntNode* next2 = head2->getLink();

	while(head1->getLink() != NULL && head2->getLink() != NULL)
	{
		if(head1->getData() <= head2->getData())
		{
			head1->setLink(head2);
			head1 = next1;
			next1 = next1->getLink();
		}
		else if(head1->getData() > head2->getData())
		{
			head2->setLink(head1);
			head2 = next2;
			next2 = next2->getLink();
		}
	}

	return head;


The problem is : What if one list reaches NULL ? Can't figure out how to do next...Thanks in advance !
helios (17574)
Then you append the remainder of the other list.
merge(null,a)=merge(a,null)=a
hentaiw (273)
IF :
List 1 : 1 3 5
List 2 : 2 4 6 7
=> 5 is NULL....simply put 6 link after 5

BUT :
List 1 : 1 3 7
List 2 : 2 4 6 9
=> 7 is NULL but can't do the same as above cuz 7>6 and 7<9
helios (17574)
???

Case 1:
a: 1 3 5
b: 2 4 6 7
r:

a: 3 5
b: 2 4 6 7
r: 1

a: 3 5
b: 4 6 7
r: 1 2

a: 5
b: 4 6 7
r: 1 2 3

a: 5
b: 4 6 7
r: 1 2 3

a: 5
b: 6 7
r: 1 2 3 4

a:
b: 6 7
r: 1 2 3 4 5

(a is empty. Copy the remained of b.)
a:
b:
r: 1 2 3 4 5 6 7

Case 2:
a: 1 3 7
b: 2 4 6 9
r:

a: 3 7
b: 2 4 6 9
r: 1

a: 3 7
b: 4 6 9
r: 1 2

a: 7
b: 4 6 9
r: 1 2 3

a: 7
b: 6 9
r: 1 2 3 4

a: 7
b: 9
r: 1 2 3 4 6

a:
b: 9
r: 1 2 3 4 6 7

(a is empty. Copy the remained of b.)
a:
b:
r: 1 2 3 4 6 7 9

EDIT: Fixed minor problem in case 2.
Last edited on
hentaiw (273)
I can't create or delete any node (that the objective of this project)...what di you mean by having R list ?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
IntNode* merge(IntNode*& head1,IntNode*& head2)
{
	IntNode* result;
	if(head1->getData() <= head2->getData())
		result = head1;
	else
		result = head2;
	
	IntNode* next1 = head1->getLink();
	IntNode* next2 = head2->getLink();

	while(head1->getLink() != NULL && head2->getLink() != NULL)
		if(head1->getData() <= head2->getData())
		{
			head1->setLink(head2);
			head1 = next1;
			next1 = next1->getLink();
		}
		else
		{
			head2->setLink(head1);
			head2 = next2;
			next2 = next2->getLink();
		}

	return result;
}


Rewrote the code again.... still sucks....

L1 : 1 3 5
L2 : 2 4 6

It will output 1 2 3 4 6 but not 5
helios (17574)
I can't create or delete any node
My example runs only move nodes (although I screwed up the wording when I wrote "copy the remainder"), but in any case they're just examples to demonstrate my original suggestion.

what di you mean by having R list ?
I accidentally deleted the part that explained that. r is the result list.

Rewrote? All you did was rename 'head' to 'result' and remove a couple of braces.
Do what I said in my first post. It works. If you don't see why it works, try doing example runs.
Last edited on
hentaiw (273)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
IntNode* merge(IntNode*& head1,IntNode*& head2)
{
	IntNode* result;
	if(head1->getData() <= head2->getData())
		result = head1;
	else
		result = head2;
	
	IntNode* next1 = head1->getLink();
	IntNode* next2 = head2->getLink();

	while(head1->getLink() != NULL && head2->getLink() != NULL)
		if(head1->getData() <= head2->getData())
		{
			head1->setLink(head2);
			head1 = next1;
			next1 = next1->getLink();
		}
		else
		{
			head2->setLink(head1);
			head2 = next2;
			next2 = next2->getLink();
		}

		if(head1->getLink() == NULL && (head1->getData() <= next2->getData()))
		{
			head2->setLink(head1);
			head1->setLink(next2);
		}
		else if(head2->getLink() == NULL && (head2->getData() <= next1->getData()))
		{
			head1->setLink(head2);
			head2->setLink(next1);
		}
		else if (head1->getLink() == NULL && (head1->getData() > next2->getData()))
		{
			while(head2->getData() <  head1->getData() && (head2->getLink() != NULL))
				head2 = head2->getLink();
			head2->setLink(head1);
		}
		else if (head2->getLink() == NULL && (head2->getData() > next1->getData()))
		{
			while(head1->getData() <  head2->getData() && (head1->getLink() != NULL))
				head1 = head1->getLink();
			head1->setLink(head2);
		}

	return result;
}


Is this what you mean ? I moved using setlink and a next1,next2 pointers... and it works fine with null in the end now...

But I input :

L1 : 1 2 3 4 5
L2 : 2 3 4 5

It outputs :

Merged : 1 2 3 3 4 4 5

I has lost one number, "2" how could this happen ?

P/S : Would the exercice be easier if it allows to create new node ?
Last edited on
helios (17574)
Would the exercice be easier if it allows to create new node ?
No.

I'm having a really hard time getting through this logic. What exactly does IntNode::SetLink() do? Are these nodes singly linked or doubly linked?

EDIT: Well, I give up. I'm left with this at the end of the first while:
http://imageshack.us/photo/my-images/842/clipboard01k.png/
Even without knowing those things I just asked, I'm fairly sure your logic is completely broken and will definitely leave you with malformed lists at the end. Start over.
Additionally, I strongly suggest not to do this:
1
2
 
head1 = next1;
next1 = next1->getLink();
And to instead do this:
 
 
head1 = head1->getLink();

EDIT 2: The main problem is that you're treating the merge operation as a sort of intertwined insertion between two lists.
There's basically two ways to merge lists (that I can think of ATM):
* Breaking the lists apart and reconstructing them through this process:
1
2
3
4
5
6
7
8
9
10
11
12
 
//[] is the empty list
//a:[] = [a]
//a:b:[] = a:(b:[]) = [a, b]
//a:b:c:[] = a:(b:(c:[])) = [a, b, c]
//head() returns the first node of the list
//tail() returns all the other nodes

merge(a,[]) = a
merge([],a) = a
merge(a,b) = if head(a)<head(b)
    then (head(a):merge(tail(a),b))
    else (head(b):merge(a,tail(b)))

* Insert-sorted each node of one list into the other list, but the list that gets nodes inserted into it and the list whose nodes are inserted don't swap responsibilities.
You would appear to be trying some weird combination of the two, which of course doesn't work.
Last edited on
hentaiw (273)
I'm really grateful for your patience...I understand the algorithm...but bad at the code...

First,this is the definition of IntNode :

1
2
3
4
5
6
7
8
9
10
11
12
13
 
	class IntNode
	{
	public:
		IntNode() : link(NULL){}
		IntNode(int theData,IntNode* theLink) : data(theData),link(theLink){}
		IntNode* getLink() {return link;}
		void setLink(IntNode* theLink) {link = theLink;}
		void setData(int theData) {data = theData;}
		int getData() {return data;}
	private:
		int data;
		IntNode *link;
	};



How I create 2 lists :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
	cout << "Insert Linked List 1,End by Negative" << endl;
	cin >> next;
	if(next >=0)
	{
		top1 = head1 = new IntNode(next,NULL);
		cin >> next;
	}
	else
		top1 = head1 = NULL;
	while(next >=0)
	{
		head1->setLink(new IntNode(next,NULL));
		head1 = head1->getLink();
		cin >> next;
	}
	head1 = top1;

	cin.ignore(1000,'\n');


The same for 2nd list.

And the faulty While LOOP :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
IntNode* merge(IntNode*& head1,IntNode*& head2)
{
	IntNode *next1 = head1->getLink();
	IntNode *next2 = head2->getLink();

	IntNode *result,*topResult;

	if(head1->getData() <= head2->getData())
	{
		result = head1;
		head1->setLink(NULL);
		head1 = next1;
		next1 = head1->getLink();
	}
	else
	{
		result = head2;
		head2->setLink(NULL);
		head2 = next2;
		next2 = head2->getLink();
	}

	topResult = result;

	//cout << head1->getData();
	//cout << head2->getData();

	while(head1->getLink() != NULL && head2->getLink() != NULL)
	{
		if(head1->getData() <= head2->getData())
		{
			head1->setLink(NULL);
			result->setLink(head1);
			head1 = next1;
			next1 = head1->getLink();
			result = result->getLink();
		}
		else
		{
			head2->setLink(NULL);
			result->setLink(head2);
			head2 = next2;
			next2 = head2->getLink();
			result = result->getLink();
		}
	}

}


With case :

a: 1 3 7
b: 2 4 6 9

I don't say that list 1 reach null mean it contains no node...but have only 1 node left which the while loop end there...

Can you just simply explain at the code level ?
Last edited on
helios (17574)
I don't have a way to do show you with code without solving it for you. I can say this, though: your merge() is completely bogus. You're approaching the problem from the wrong angle and it simply will not work like this. You have to start it over from scratch and think up something completely different.
hentaiw (273)
I wrote the code,again,and now have success :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
 
IntNode* merge(IntNode*& head1,IntNode*& head2)
{
	IntNode *next1 = head1->getLink();
	IntNode *next2 = head2->getLink();

	IntNode *result,*topResult;

	if(head1->getData() <= head2->getData())
	{
		result = head1;
		head1->setLink(NULL);
		head1 = next1;
		next1 = head1->getLink();
	}
	else
	{
		result = head2;
		head2->setLink(NULL);
		head2 = next2;
		next2 = head2->getLink();
	}

	topResult = result;



	while(head1->getLink() != NULL && head2->getLink() != NULL)
	{
		if(head1->getData() <= head2->getData())
		{
			head1->setLink(NULL);
			result->setLink(head1);
			head1 = next1;
			next1 = head1->getLink();
			result = result->getLink();
		}
		else
		{
			head2->setLink(NULL);
			result->setLink(head2);
			head2 = next2;
			next2 = head2->getLink();
			result = result->getLink();
		}
	}

	cout << head1->getData();
	cout << head2->getData();
	cout << result->getData();

	if(head1->getLink() == NULL)
	{
		while(head2->getData() <= head1->getData())
		{
			head2->setLink(NULL);
			result->setLink(head2);
			head2 = next2;
			next2 = head2->getLink();
			result = result->getLink();
		}
		result->setLink(head1);
		result = result->getLink();
		result->setLink(head2);
	}
	else if(head2->getLink() == NULL)
	{
		while(head1->getData() <= head2->getData())
		{
			head1->setLink(NULL);
			head1 = next1;
			result->setLink(head2);
			result = result->getLink();
		}
		result->setLink(head2);
		result = result->getLink();
		result->setLink(head1);
	}	
	
	return topResult;
}


I handled the case when list1 or list2 contain only 1 node...

This code now work well with all the cases up to now...

Do you have any other suggestion ?

If data from list1 <= list2 then result link to list1,move forward 1 item from list 1 by using next pointer...because if I use head1->setLink(NULL); I'll have lost nodes...that's why I put pointer next1 = head1->getLink() in order to backup the memory for the remaining in list 1...and so does list 2.

It works well,but looks ugly...I'd love to have some ufeful tips of yours....
If not,I thank you anyway...your opinions always help...Thanks again...
Last edited on
Topic archived. No new replies allowed.