C++

Forum

 
Reverse Linked List...

hentaiw (273)
I wrote this for the to reverse a linked list,to have the parameter point to the end of the list and rearrange all the nodes without creating or deleting any node.But it doesn't seem to work...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
IntNode* reverse(IntNode* theHead)
{
	IntNode *current,*next1,*next2;

	current = theHead;
	next1 = current->getLink();
	next2 = next1->getLink();

	while(next2->getLink() != NULL)
	{
		next1->setLink(current);

		current = next1;
		next1 = next2;
		next2 = next2->getLink();
	}
	if(next2->getLink() == NULL)
		next2->setLink(next1);
	theHead = next2;
	return theHead;
}


Could somebody help me ? Thanks in advance.
hentaiw (273)
OK after few edit I got it right,but I still need suggestions...Please have some opinion~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
IntNode* reverse(IntNode* theHead)
{
	IntNode *current,*next1,*next2;

	current = theHead;
	next1 = current->getLink();
	next2 = next1->getLink();

	while(next2->getLink() != NULL)
	{
		next1->setLink(current);
		theHead->setLink(NULL);
		current = next1;
		next1 = next2;
		next2 = next2->getLink();
	}
	if(next2->getLink() == NULL)
	{
		next1->setLink(current);
		next2->setLink(next1);
	}
	theHead = next2;
	return theHead;
}
hentaiw (273)
My final version,allows the case of 3 nodes or less...but still look very buggy...Need your useful opinions.

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
 
IntNode* reverse(IntNode* theHead)
{
	IntNode *current,*next1,*next2;

	if(theHead->getLink() == NULL)
		return theHead;
	else
		current = theHead;
	next1 = current->getLink();
	if(next1->getLink() == NULL)
	{
		current->setLink(NULL);
		next1->setLink(current);
		theHead = next1;
		return theHead;
	}
	next2 = next1->getLink();
	current->setLink(NULL);
	while(next2->getLink() != NULL)
	{
		next1->setLink(current);
		current = next1;
		next1 = next2;
		next2 = next2->getLink();
	}
	if(next2->getLink() == NULL)
	{
		if(current == theHead)
			current->setLink(NULL);
		next1->setLink(current);
		next2->setLink(next1);
		theHead = next2;
	}
	return theHead;
}
Last edited on
codekiddy (783)
hi hentaiw,
I've found my old liked list in my Recycle Bin, you may find it useful by comparing my List with yours to solve your list!!

pointer.h (base class with main pointers)

1
2
3
4
5
6
7
8
9
10
11
12
 
#pragma once

class Pointer {
private:
	Pointer* next;
	Pointer* previous;
public:
	Pointer* get_next() const { return next; }
	Pointer* get_previous() const {return previous; }
	void set_next( Pointer* ptr ) { next = ptr; }
	void set_previous( Pointer* ptr) { previous = ptr; }
};


List.h (definition of the List class)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#pragma once
#include "Pointer.h"

class List : public Pointer {
private:
	Pointer* front;
	Pointer* back;
public:
	List() : front( nullptr ), back( nullptr ) {}

	void InsertList(List& lst);
	void InsertAtBegining( Pointer* ptr );
	void InsertAtTheEnd( Pointer* ptr );
	void Insert_member(Pointer* ptr, Pointer* behind = nullptr );

	void Delete_member(Pointer* ptr);

	Pointer* getFront() const { return front; }
	Pointer* getBack() const { return back; }
};


List.cpp (definition of List class metods)
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
 
#include "List.h"

void List::Insert_member( Pointer* ptr, Pointer* behind ) {

	if( behind != nullptr ) {
		if( behind->get_next() != nullptr )
			behind->get_next()->set_previous( ptr );
		else
			back = ptr;
		ptr->set_next( behind->get_next() );
		behind->set_next( ptr );
	}

	else {
		ptr->set_next( front );
		if( front != nullptr )
			front->set_previous( ptr );
		front = ptr;
	}

	ptr->set_previous( behind );
}




void List::Delete_member( Pointer* ptr ) {

	if( ptr->get_next() != nullptr )
		ptr->get_next()->set_previous( ptr->get_previous() );
	else
		back = ptr->get_previous();

	if( ptr->get_previous() != nullptr )
		ptr->get_previous()->set_next( ptr->get_next() );
	else
		front = ptr->get_next();
}


void List::InsertAtBegining( Pointer* ptr ) {
	ptr->set_next( front );
	front->set_previous( ptr );
	front = ptr;
	ptr->set_previous( nullptr );
}




void List::InsertAtTheEnd( Pointer* ptr ) {
	back->set_next( ptr );
	ptr->set_previous( back );
	back = ptr;
	ptr->set_next( nullptr );
}


void List::InsertList(List& lst) {
	Pointer* count = lst.getFront();
	do InsertAtBegining( count );
	while ( ( count = count->get_next() )->get_next() != nullptr );
}


Topic archived. No new replies allowed.