Doubly Linked List Rotation (k=3)

Initial Doubly Linked List

1
↔
2
↔
3
↔
4
↔
5
↔
6
↔
7
↔
8

This is our initial doubly linked list. Each node contains a value and has pointers to both the previous and next nodes.

A doubly linked list allows us to traverse in both directions, as indicated by the bidirectional arrows (↔).

Our task is to rotate this list using k=3, which will result in groups of 3 nodes being reversed.

Step 1: Identifying Groups for Rotation

1
↔
2
↔
3
↔
4
↔
5
↔
6
↔
7
↔
8

First, we divide the list into groups of k=3 nodes each:

  • Group 1: 1 ↔ 2 ↔ 3
  • Group 2: 4 ↔ 5 ↔ 6
  • Group 3: 7 ↔ 8 (this group has only 2 nodes since we don't have enough nodes to form a complete group of 3)

Each of these groups will be rotated independently while maintaining the connections between groups.

Step 2: Reversing First Group

3
↔
2
↔
1
↔
4
↔
5
↔
6
↔
7
↔
8

Now we reverse the first group (1 ↔ 2 ↔ 3):

The links between nodes are reversed, changing the order to 3 ↔ 2 ↔ 1.

To reverse a group:

  • We switch the next and previous pointers of each node
  • Node 3 becomes the new head of this group
  • Node 1 becomes the new tail of this group

Step 3: Reversing Second Group

3
↔
2
↔
1
↔
6
↔
5
↔
4
↔
7
↔
8

Next, we reverse the second group (4 ↔ 5 ↔ 6):

Following the same process, the order changes to 6 ↔ 5 ↔ 4.

The pointers are adjusted so that:

  • Node 1 (last node of first group) connects to node 6 (first node of reversed second group)
  • Node 6 becomes the new head of this group
  • Node 4 becomes the new tail of this group

Step 4: Reversing Final Group

3
↔
2
↔
1
↔
6
↔
5
↔
4
↔
8
↔
7

Finally, we reverse the last group (7 ↔ 8):

After reversal, the order becomes 8 ↔ 7.

Since this group doesn't have k=3 nodes (it only has 2), we still reverse it following the same rules:

  • Node 4 (last node of second group) connects to node 8 (first node of reversed third group)
  • The pointers within the group are reversed

Final Result: Rotated Doubly Linked List

3
↔
2
↔
1
↔
6
↔
5
↔
4
↔
8
↔
7

We have successfully rotated the doubly linked list with k=3!

Our original list: 1 ↔ 2 ↔ 3 ↔ 4 ↔ 5 ↔ 6 ↔ 7 ↔ 8

Has been transformed to: 3 ↔ 2 ↔ 1 ↔ 6 ↔ 5 ↔ 4 ↔ 8 ↔ 7

Each group of k=3 nodes (or less for the last group) has been reversed, and the connections between groups have been maintained.

The doubly linked list structure remains intact, allowing traversal in both directions.