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
1. Search the first node is less than the previous, the start of misplacing nodes is the previous one
2. Loop through till next node is greater than the start node,
3. If step 2 cannot be found, the end of misplacing nodes is the last node
4. Correct the nodes
/*
============================================================================
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 . . .