Given a linked list, reverse alternate nodes and append at the end | GeeksforGeeks

Given a linked list, reverse alternate nodes and append them to end of list. Extra allowed space is O(1)
Examples

Input List:  1->2->3->4->5->6  Output List: 1->3->5->6->4->2

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;

}

Read full article from Given a linked list, reverse alternate nodes and append at the end | GeeksforGeeks