Post date: Jul 03, 2013 2:21:42 AM
Problem
Sublist of a sorted (ascending order)link list is reversed...correct it
1--->2--->3--->4--->8--->7--->6--->5--->9--->10--->NULL
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Correct a sorted linked list with a reversed sublist
Created Date : 3-July-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <stack>
#include <vector>
typedef struct LinkedNode{
int data;
struct LinkedNode* next;
} LINKEDNODE;
using namespace std;
void AddNode(LINKEDNODE **head, int data)
{
LINKEDNODE *ln = new LINKEDNODE;
ln->data = data;
ln->next = NULL;
if(*head == NULL){
*head = ln;
return;
}
LINKEDNODE *node = *head;
while(node->next != NULL){
node = node->next;
}
node->next = ln;
}
void DeleteList(LINKEDNODE *head)
{
while(head != NULL){
LINKEDNODE *node = head;
head = head->next;
delete node;
}
}
void PrintList(LINKEDNODE *head)
{
while(head != NULL){
cout << setw(3) << left << head->data;
head = head->next;
}
cout << endl;
}
void CorrectSortedLinkedList(LINKEDNODE *head)
{
if(head == NULL){
cout << "The list is empty" << endl;
return;
}
LINKEDNODE *node = head;
if(node->next == NULL){
cout << "Only one node in the list" << endl;
return;
}
stack<int> s;
LINKEDNODE *start(NULL), *end(NULL);
while(node->next != NULL){
if(start == NULL && node->data > node->next->data){
start = node;
}
else if(start != NULL && node->next->data > start->data){
end = node;
s.push(node->data);
break;
}
if(start != NULL){
s.push(node->data);
}
node = node->next;
}
if(end == NULL){
s.push(node->data);
}
while(!s.empty()){
start->data = s.top();
s.pop();
start = start->next;
}
}
void DoTest(int* arr, int len)
{
LINKEDNODE *head = NULL;
for(int i = 0; i <len; ++i){
AddNode(&head, arr[i]);
}
cout << "Before correcting" << endl;
PrintList(head);
CorrectSortedLinkedList(head);
cout << "After correcting" << endl;
PrintList(head);
DeleteList(head);
cout << "-------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int array[] = {1, 2, 3, 4, 8, 7, 6, 5, 9, 10};
DoTest(array, sizeof(array)/sizeof(array[0]));
int array1[] = {1};
DoTest(array, sizeof(array1)/sizeof(array1[0]));
int array2[] = {2, 1};
DoTest(array2, sizeof(array2)/sizeof(array2[0]));
int array3[] = {3, 2, 1};
DoTest(array3, sizeof(array3)/sizeof(array3[0]));
int array4[] = {1, 2, 3, 10, 9, 8, 7, 6, 5, 4};
DoTest(array4, sizeof(array4)/sizeof(array4[0]));
return 0;
}
Output
Before correcting
1 2 3 4 8 7 6 5 9 10
After correcting
1 2 3 4 5 6 7 8 9 10
-------------------------------
Before correcting
1
Only one node in the list
After correcting
1
-------------------------------
Before correcting
2 1
After correcting
1 2
-------------------------------
Before correcting
3 2 1
After correcting
1 2 3
-------------------------------
Before correcting
1 2 3 10 9 8 7 6 5 4
After correcting
1 2 3 4 5 6 7 8 9 10
-------------------------------
Press any key to continue . . .