Wednesday, August 15, 2012

Reverse a linked list in group of k

This is one of a candidate interview question. I don't see any practical application of this-
Given a linked list, reverse the list in groups of size k. 
I am sure it is not clear to you, so here is a example-
Input -    1=>2=>3=>4=>5=>6=>7=>8
Output -  3=>2=>1=>6=>5=>4=>8=>7

Try solving it yourself before going through the code.
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
int v;
struct node *next;
} node;

node * revk(node *head, int k)
{
int i = 1;
node *p, *b, *s1, *s2, *t;
p = head;
b = NULL;
s1 = NULL;
s2 = head;

while (p)
{
t = p;
p = p->next;
if (t)
t->next = b;
b = t;

if (i == k)
{
if (s1)
s1->next = b;
else
head = b;
s1 = s2;
s2 = p;
i = 0;
}
i++;
}
s1->next = b;
s2->next = NULL;
return head;
}

void print(node *head)
{
node *p = head;
while (p)
{
printf("%d -> ", p->v);
p = p->next;
}
printf("$\n");
}

void insert(node **t, int v)
{
node *p = malloc(sizeof(node));
p->v = v;
p->next = NULL;
(*t)->next = p;
*t = p;
}

int main(int argc, char *argv[])
{
node *head, *tail = NULL;
head = malloc(sizeof(node));
head->next = NULL;
head->v = 1;
tail = head;
insert(&tail, 2);
insert(&tail, 3);
insert(&tail, 4);
insert(&tail, 5);
insert(&tail, 6);
insert(&tail, 7);
insert(&tail, 8);

print(head);

head = revk(head, 3);

print(head);

tail = head;

while (tail)
{
head = tail;
tail = tail->next;
free(head);
}

printf("\n");
return 0;
}

No comments:

Post a Comment