How to reverse each half of a doubly linked list? C++

Question

Does anyone have any ideas how to reverse each half of a doubly linked list?
I know how to reverse the whole list, but how to reverse each half in the same list?

Let’s assume the list is even, and sorting doesn’t matter.

For example:
1 <=> 2 <=> 6 <=> 3 <=> 7 <=> 9
Expected output:
6 <=> 2 <=> 1 <=> 9 <=> 7 <=> 3

Answer 1

Since it is a double linked list you have pointers to both prev and next items.
1. Start from the second item: node = head->next (check on NULL)
2. Swap values of node->prev->value and node->next->value
3. Move 3 items forward: node = node->next->next->next.
But before moving you should check that all of three next pointers are not NULL.
If any of them is NULL or node->next (after assignment) is NULL, you are done (break loop).
4 Repeat from step 2.

Answer 2

If you check on the end of the list on each iteration then yes it will work with any size.
An algorithm should be as folow:

check on (head != NULL && head->next != NULL)
node = head->next

beginning of a loop:
check on (node->next != NULL)
swap values

for(int i = 0; i < 3; ++i){ //move forward 3 items
node = node->next
check on (node != NULL)
}

end of the loop (continue from the beginning of a loop)

if any of the checks on NULL fails you are done.

Answer 3

andriy kan does this work with a list of any size?

Answer 4

andriy kan Thanks! I’ll try that