Problem: partially revert a linked list
Given a HEAD pointer to a linked list and an OFFSET pointer pointing to a node in the linked list. You are asked to write a C/C++ subroutine to revert the part of the list from HEAD to OFFSET:
You are NOT allowed to use recursion. Please follow the definition of the type and function as shown below:
And here is my solution:
I partial revert the linked list using a method like a bubble sort way without comparing. However I have made a little change here to make it look like a C++ style.
#include <iostream>
class Node
{
public:
int value;
Node* next;
public:
static Node* Revert( Node*, Node* );
};
Node* Node::Revert( Node* head, Node* offset )
{
Node *p1, *p2;
int tval;
while( head != offset )
{
p1 = head;
p2 = head->next;
while( p2 != offset )
{
tval = p1->value;
p1->value = p2->value;
p2->value = tval;
p1 = p2;
p2 = p1->next;
}
tval = p1->value;
p1->value = p2->value;
p2->value = tval;
offset = p1;
}
return head;
}
// Here is the test code
int main( int argc, char* argv[] )
{
Node* head;
Node* tail;
Node* iter;
//generate the linked list
head = new Node;
head->value = 1;
head->next = NULL;
tail = head;
for ( int i = 2; i < 9; i++ )
{
iter = new Node;
iter->value = i;
iter->next = NULL;
tail->next = iter;
tail = iter;
}
// Output the original list
for( iter = head; iter != NULL; iter = iter->next )
{
std::cout << iter->value << std::endl;
}
head = Node::Revert( head, tail );
std::cout<< "--------------------" << std::endl;
// Output the Reverted list
for( iter = head; iter != NULL; iter = iter->next )
{
std::cout << iter->value << std::endl;
}
return 0;
}
