C++程序 按块旋转链表

给定长度为n的链表和块长度 k ，通过一个数字 d ，以环形方式向右/向左旋转每个块。如果 d 为正数，则向右旋转，否则向左旋转。

示例：

输入： 1->2->3->4->5->6->7->8->9->NULL,
k = 3
d = 1
输出： 3->1->2->6->4->5->9->7->8->NULL
解释： 这里块的大小为3，朝右旋转（因为d是正数）1次。

输入： 1->2->3->4->5->6->7->8->9->10->
11->12->13->14->15->NULL,
k = 4
d = -1
输出： 2->3->4->1->6->7->8->5->10->11->
12->9->14->15->13->NULL
解释： 在链表的末尾，剩余的节点少于k，即在k为4时仅剩3个节点。同样需要根据d将这三个节点旋转。

这个想法是，如果d的绝对值大于k的值，则将链表旋转d % k次。如果d为0，则根本不需要旋转链表。

// C++程序用于块旋转链接列表
//block wise 
#include<bits/stdc++.h>
using namespace std;
  
//链接列表节点
class Node 
{ 
    public:
    int data; 
    Node* next; 
}; 
  
//递归函数以旋转
//一个块
Node* rotateHelper(Node* blockHead, 
                   Node* blockTail, 
                   int d, Node** tail, 
                   int k) 
{ 
    if (d == 0) 
        return blockHead; 
  
    //顺时针旋转
    if (d > 0) 
    { 
        Node* temp = blockHead; 
        for (int i = 1; temp->next->next && 
                 i < k - 1; i++) 
            temp = temp->next; 
  
        blockTail->next = blockHead; 
        *tail = temp; 
        return rotateHelper(blockTail, temp, 
                            d - 1, tail, k); 
    } 
  
    //逆时针旋转
    if (d < 0) 
    { 
        blockTail->next = blockHead; 
        *tail = blockHead; 
        return rotateHelper(blockHead->next, 
                            blockHead, d + 1, 
                            tail, k); 
    } 
} 
  
//函数以块方式旋转链接列表
Node* rotateByBlocks(Node* head, 
                     int k, int d) 
{ 
    //如果长度为0或1，则返回头部 
    if (!head || !head->next) 
        return head; 
  
    //如果旋转度为0，则返回头部 
    if (d == 0) 
        return head; 
  
    Node* temp = head, *tail = NULL; 
  
    //遍历直到该块的最后一个元素 
    int i; 
    for (i = 1; temp->next && i < k; i++) 
         temp = temp->next; 
  
    //存储下一个块的第一个节点
    Node* nextBlock = temp->next; 
  
    //如果该块的节点少于k，则也旋转该块
    if (i < k) 
        head = rotateHelper(head, temp, 
                            d % k, &tail, i); 
    else
        head = rotateHelper(head, temp, 
                            d % k, &tail, k); 
  
    //将下一个块的新头部追加到该块的尾部
    tail->next = rotateByBlocks(nextBlock, 
                                k, d % k); 
  
    //返回更新后的链接列表的头部
    return head; 
} 
  
//实用函数
//将节点压入链表
void push(Node** head_ref, 
          int new_data) 
{ 
    Node* new_node = new Node; 
    new_node->data = new_data; 
    new_node->next = (*head_ref); 
    (*head_ref) = new_node; 
} 
  
//打印链接列表的函数
void printList(Node* node) 
{ 
    while (node != NULL) 
    { 
        cout << node->data << " "; 
        node = node->next; 
    } 
} 
  
// 驱动程序
int main() 
{ 
    //从空列表开始
    Node* head = NULL; 
  
    //创建一个列表 1->2->3->4->5->6->7->8->9->NULL 
    for (int i = 9; i > 0; i -= 1) 
        push(&head, i); 
  
    cout << 
    "Given linked list "; 
    printList(head); 
  
    // k是块大小，d是每个块中旋转的次数。
    int k = 3, d = 2; 
    head = rotateByBlocks(head, k, d); 
  
    cout <<
    "Rotated by blocks Linked list "; 
    printList(head); 
  
    return (0); 
} 

输出：

给定的链接列表
1 2 3 4 5 6 7 8 9
以块旋转的链接列表
2 3 1 5 6 4 8 9 7