Turbo C++ - Reverse Singly Linked List
I have given here Turbo C++ sample code to reverse a singly linked list.
Reversing a singly linked list is very easy. The SLinkList* Reverse(SLinkList *head) function is about ten lines of code that does the magic.
Singly Linked List, Doubly Linked List, Singly Linked Circular List and Doubly Linked Circular List are an important data structure used in C++ applications.
Related Links:
- Turbo C++ - Reverse Singly Linked List
- Turbo C++ - Singly Linked Circular List
- Turbo C++ - Doubly Linked List
- Turbo C++ - Singly Linked List
- Visual C++ Program to Reverse Singly Linked List
- Visual C++ Program for Singly Linked Circular List
- Visual C++ Program for Doubly Linked List
- Visual C++ Program for Singly Linked List
- Java - Reverse Singly Linked List
- Java - Singly Linked Circular List
- Java - Doubly Linked List
- Java - Singly Linked List
- C# - Reverse Singly Linked List
- C# - Singly Linked Circular List
- C# - Doubly Linked List
- C# - Singly Linked List
Source Code
#include <iostream.h>
struct SLinkList
{
int data;
SLinkList *next;
SLinkList();
SLinkList(int value);
SLinkList* InsertNext(int value);
int DeleteNext();
void Traverse(SLinkList *node = NULL);
};
SLinkList::SLinkList() : data(0), next(NULL)
{
}
SLinkList::SLinkList(int value) : data(value), next(NULL)
{
}
SLinkList* SLinkList::InsertNext(int value)
{
SLinkList *node = new SLinkList(value);
if(this->next == NULL)
{
// Easy to handle
node->next = NULL; // already set in constructor
this->next = node;
}
else
{
// Insert in the middle
SLinkList *temp = this->next;
node->next = temp;
this->next = node;
}
return node;
}
int SLinkList::DeleteNext()
{
if(this->next == NULL)
return 0;
SLinkList *pNode = this->next;
this->next = this->next->next; // can be NULL here
delete pNode;
return 1;
}
void SLinkList::Traverse(SLinkList *node)
{
if(node == NULL)
node = this;
cout << "\n\nTraversing in Forward Direction\n\n";
while(node != NULL)
{
cout << node->data;
cout << "\n";
node = node->next;
}
}
SLinkList* Reverse_With_Bubble(SLinkList *head)
{
SLinkList *testnode = NULL;
if(head == NULL)
return head;
while(1)
{
SLinkList *p = head;
if(p->next == testnode)
break;
while(1)
{
int temp = p->data;
p->data = p->next->data;
p->next->data = temp;
p = p->next;
if(p->next == testnode)
{
testnode = p;
break;
}
}
}
return head;
}
SLinkList* Reverse(SLinkList *head)
{
if(head == NULL)
return head;
SLinkList *cp = head;
SLinkList *prev = NULL;
while(cp != NULL)
{
SLinkList *next = cp->next;
cp->next = prev;
prev = cp;
cp = next;
}
head = prev;
return head;
}
SLinkList* Reverse_with_copy(SLinkList *head)
{
SLinkList *p = head;
SLinkList *newhead = NULL;
while(1)
{
if(p == NULL)
return newhead;
SLinkList *newnode = new SLinkList(p->data);
newnode->next = newhead;
newhead = newnode;
p = p->next;
}
return newhead;
}
int main()
{
SLinkList *head = new SLinkList(1);
SLinkList *p = head->InsertNext(2);
p = p->InsertNext(3);
p = p->InsertNext(4);
p = p->InsertNext(5);
p = p->InsertNext(6);
p = p->InsertNext(7);
p = p->InsertNext(8);
head->Traverse();
SLinkList *newhead = Reverse(head);
newhead->Traverse();
cout << "\n";
return 0;
}
Output
Traversing in Forward Direction
1
2
3
4
5
6
7
8
Traversing in Forward Direction (After Reversal)
8
7
6
5
4
3
2
1
|
|