C++程序链表的顺时针旋转

给定一个单链表和一个整数 K ，任务是将链表顺时针向右旋转 K 个位置。

例子:

输入: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, K = 2

输出: 4 -> 5 -> 1 -> 2 -> 3 -> NULL

输入: 7 -> 9 -> 11 -> 13 -> 3 -> 5 -> NULL, K = 12

输出: 7 -> 9 -> 11 -> 13 -> 3 -> 5 -> NULL

做法: 为了顺时针旋转链表，请先检查给定的k是否大于链表中节点的数量。遍历列表并找到链表的长度，然后将其与k进行比较，如果小于则继续，否则通过将其与列表的长度取模来在链表大小范围内减少它。
然后从链表的长度中减去k的值。现在，问题已经转化为链表的左旋，因此请按照以下过程进行操作:

将第k个节点的下一个节点更改为NULL。
将最后一个节点的下一个节点更改为先前的头节点。
将头更改为第(k+1)个节点。

为了实现这一点，需要指向第k个节点、第(k+1)个节点和最后一个节点的指针。

下面是上述做法的实现:

// C++实现方法
#include <bits/stdc++.h>
using namespace std;

/* 链表节点 */
class Node {
public:
    int data;
    Node* next;
};

/* 推送节点的辅助函数 */
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;
    }
    cout << "NULL";
}

// 将给定的链接列表顺时针旋转k次，并返回更新后的头指针
Node* rightRotate(Node* head, int k)
{

    // 如果链接列表为空
    if (!head)
        return head;

    // len用于存储链接列表的长度
    // tmp将在此循环后指向最后一个节点
    Node* tmp = head;
    int len = 1;
    while (tmp->next != NULL) {
        tmp = tmp->next;
        len++;
    }

    // 如果k大于链接列表的大小
    if (k > len)
        k = k % len;

    // 从长度中减去以将其转换为左旋转
    k = len - k;

    // 如果需要旋转，则返回头节点
    if (k == 0 || k == len)
        return head;

    // 当前节点将在此循环后指向kth或NULL
    Node* current = head;
    int cnt = 1;
    while (cnt < k && current != NULL) {
        current = current->next;
        cnt++;
    }

    // 如果当前节点为NULL，则k等于列表中的节点数
    // 在这种情况下不要更改列表
    if (current == NULL)
        return head;

    // 当前节点指向第k个节点
    Node* kthnode = current;

    // 将最后一个节点的下一个更改为以前的头
    tmp->next = head;

    // 将头更改为（k+1）th节点
    head = kthnode->next;

    // 将kth节点的下一个更改为NULL
    kthnode->next = NULL;

    // 返回更新后的头指针
    return head;
}

// 主函数
int main()
{

    /* 构建链接列表:
     1->2->3->4->5 */
    Node* head = NULL;
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    int k = 2;

    // 旋转链接列表
    Node* updated_head = rightRotate(head, k);

    // 打印旋转后的链接列表
    printList(updated_head);

    return 0;
}