Friday, March 11, 2011

write a function to reverse every alternate k nodes in linked list

Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm.
Example:
Inputs: 1->2->3->4->5->6->7->8->9->NULL and k = 3
Output: 1->2->3->6->5->4->8->7->9->NULL.



#include
#include

/* Link list node */
struct node
{
int data;
struct node* next;
};

/* Reverses alternate k nodes and
returns the pointer to the new head node */
struct node *reverse (struct node *head, int k)
{
struct node* current = head;
struct node* next;
struct node* prev = NULL;
int count = 0;

/*reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}
if(head != NULL)
head->next = current;

/* Do not reverse next k nodes */
count = 0;
while(count < k-1 && current != NULL )
{
current = current->next;
count++;
}

/* next is now a pointer to (k+1)th node
Recursively call for the list starting from current.
And make rest of the list as next of first node */
if(current != NULL)
{ current->next = reverse(current->next, k); }

/* prev is new head of the input list */
return prev;
}

/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */
new_node->next = (*head_ref);

/* move the head to point to the new node */
(*head_ref) = new_node;
}

/* Function to print linked list */
void printList(struct node *node)
{
int count = 0;
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
count++;
}
}

/* Drier program to test above function*/
int main(void)
{
/* Start with the empty list */
struct node* head = NULL;

// create a list 1->2->3->4->5...... ->20
for(int i = 20; i > 0; i--)
push(&head, i);

printf("\n Given linked list \n");
printList(head);
head = reverse(head, 3);

printf("\n Reversed Linked list \n");
printList(head);

getchar();
return(0);
}

Output:
Given linked list
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Reversed Linked list
3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19

4 comments :

MK said...
This comment has been removed by the author.
MK said...
This comment has been removed by the author.
MK said...

Is there a typo in the Output at the very beginning of the post? 8 and 7 are reversed in the output, but after reading the post I think only 4,5,6 should be reversed in the output and nothing else?

Unknown said...

@Mayuresh....hey i m reversing the 1st K nodes in SLL then leaving next K nodes same & repeating the same fro n-2k nodes..just try to dry run the code carefully, u will get it...hope it will make your clear..let me know if still anything wrong