Tuesday, March 30, 2010

K Reverse linked list

Given a linked list, we need to write a function that reverses the nodes of a linked list ‘k’ at a time and returns modified linked list.

The following are the constraints given:

  • You have to retain the memory address of the nodes without modifying it i.e. you can’t just interchange the values in the nodes
  • Only constant memory is allowed

For example the linked list given is as follows:

Linked List : 1->2->3->4->5->6->7->8->9->10->11 -> null

For k = 2

Return Value: 2->1->4->3->6->5->8->7->10->9->11 ->null

For k = 3

Return value: 3->2->1->6->5->4->9->8->7->10->11 -> null

Solution:



#include "iostream"
using namespace std;

const int N = 10;

//Linked List Class
class LinkedList
{
private:
struct Node{
int data;
struct Node *next;
Node(){next = NULL;};
};
struct Node * Head;
public:
LinkedList();
bool create();
void print();
void reverse(int k);
};

//Print the List
void LinkedList::print()
{
Node *p = Head;
while(p)
{
cout <<>data << " ";
p = p->next;
}
cout << endl;
}

//CTR
LinkedList::LinkedList()
{
Head = NULL;
}

//Create the Linked List 1->2->3->4->5->6->7->8->9->10
bool LinkedList::create()
{
Head = new (struct Node);
Head->data = 1;
Node *p=Head;
Node *t;
for(int i = 2; i <= N; i++){
t = new (struct Node);
t->data = i;
p->next = t;
p = p->next;
}
return true;

}

//Reverse the Linked List within K nodes
void LinkedList::reverse(int k)
{
Node *p = Head;
Node *q = Head;
Node *t = p->next;
Node *r = p->next;
Node *last = p;
p->next = NULL;
int i = 1;
bool flag = false;
while(r)
{
//reverse the list
r = r->next;
t->next = p;
q->next = r;
p = t;
t = r;

i++;
// when k nodes are reversed, start from the next k nodes
if(i >= k||r == NULL){
i = 1;
if(!flag){
Head = p;
flag = true;
}
else
last->next = p;

last = q; // link the last k nodes to the next k nodes
p = r;
q = r;
if(p){
r = p->next;
t = p->next;
}
else{
r= NULL;
t = NULL;
}
}

}
}


int main(int argc, char* argv[])
{
LinkedList L;
L.create();
L.print();
L.reverse(4);
L.print();
return 0;
}




No comments: