Thread: Reverse K nodes of a List

Given a list, you have to write a program to reverse every K nodes of the list, if numbers of nodes in list is not multiple of K then leave the last remaining nodes as it is.

Ex:
List 1:
1->2->3->4->5->6->7->8->9

given k =3
output will be
3->2->1->6->5->4->9->8->7

If list is
1->2->3->4->5->6->7->8
and k=3, then output should be
3->2->1->6->5->4->7->8

I have made a try ..kindly check it out...

listptr reverse_kadj(listptr head, int k)
{
if(!(head && head->link))
return head;
listptr start_node,tmp;
int end_flag = 0;
listptr ptr = head;
listptr prev_start_node;
listptr next_start_node;
int i;
while(1)
{
for(i=0,start_node = ptr;i<k-1;i++,ptr = ptr->link)
{
if(!ptr)
{
end_flag = 1;
break;
}
}
if(!ptr || end_flag == 1)
break;
next_start_node = ptr->link;
tmp = reverse_modify(start_node, next_start_node);
if(start_node == head)
head = tmp;
else
prev_start_node->link = tmp;
prev_start_node = start_node;
ptr = next_start_node;
}
return head;
}

listptr reverse_modify(listptr start_node, listptr next_start_node)
{
listptr trail, middle;
listptr lead = start_node;
middle = next_start_node;
while(lead != next_start_node)
{
trail = middle;
middle = lead;
lead = lead->link;
middle->link = trail;
}
return middle;
}

Good implementation. We rarely see them in java.

Code:

void kreverse(node **s, int n)
{
        node *tt1, *t1,*t2,*t3;
        tt1 = t1 = t2 = t3 = *s;
        t2 = t2->next;n--;
        while (t2 != NULL && n--)
        {
                t3 = t2->next;
                t2->next = t1;
                t1 = t2;
                t2 = t3;
        }
        if (tt1 != t3)
                tt1->next = t3;
        *s = t1;
        return ;
}

Avi
Avi Dullu&#039;s Code Arena