How to reverse every k element of a linked list?

Question

Possible Duplicate:
Reverse every k nodes of a linked list

Say the linked list is <1,3,6,4,8,9,0,2>. Calling reversek(3) would result in <6,3,1,9,8,4,2,0>. I have written the reverse function which may be used as a helper function in reversek. Here's my reverse function which reverses from a given starting point to a given ending point:

    void List::reverse(Node * & start, Node * & end)
    {
    Node *pter = start;
    while (pter != NULL) 
    {
         Node *tmp = pter->next;
         pter->next = pter->prev;
         pter->prev = tmp;
         if (tmp == NULL) 
         {
            endPoint = startPoint;
            startPoint = pter;
         }
       pter = tmp;
    }

I'm confused about how to implement reversek, any help is appreciated.

at the end, the start pointer must point at the new head of the array — SKLAK, Sep 26 '12 at 22:33
@SKLAK: whether it's your post or not is irrelevant, this question has already been asked and various solutions proposed. — Matthieu M., Sep 27 '12 at 09:41

score 0 · Answer 1 · answered Sep 26 '12 at 22:30

Try something like -

Have 2 pointers (P1, P2) to linked list head element.
One is used for traversing the list(P1). While the other(P2) is used for swapping the elements once the traversing point is reached 3rd node in the list.
Now move both the pointers to 4th node. And again continue P1 traversing rest of the list.

Here you have to keep track of when every 3rd node is reached by P1. Here it is 3 for example, but it depends on function argument.

How to reverse every k element of a linked list?

1 Answers1