# Given a linked list, reverse alternate nodes and append at the end?

341 views
Given a linked list, reverse alternate nodes and append at the end?
posted Apr 16, 2014

Suppose Your Input is `2->4->6->8->0` The expected output is `2->6->0->8->4`

The idea is to maintain two linked lists, one list of all odd positioned nodes (2, 6, 0 in above example) and other list of all even positioned nodes (6 and 8 in above example).

Algorithm
1) Traverse the given linked list which is considered as odd list. Do following for every visited node.
……a) If the node is even node, remove it from odd list and add it to the front of even node list. Nodes are added at front to keep the reverse order.
2) Append the even node list at the end of odd node list.

``````void rearrange(struct node *odd)
{
// If linked list has less than 3 nodes, no change is required
if (odd == NULL || odd->next == NULL || odd->next->next == NULL)
return;

// even points to the beginning of even list
struct node *even = odd->next;

// Remove the first even node
odd->next = odd->next->next;

// odd points to next node in odd list
odd = odd->next;

// Set terminator for even list
even->next = NULL;

// Traverse the  list
while (odd && odd->next)
{
// Store the next node in odd list
struct node *temp = odd->next->next;

// Link the next even node at the beginning of even list
odd->next->next = even;
even = odd->next;

// Remove the even node from middle
odd->next = temp;

// Move odd to the next odd node
if (temp != NULL)
odd = temp;
}

// Append the even list at the end of odd list
odd->next = even;
}
``````