C++程序 旋转链表

给定一个单链表，将链表逆时针旋转k个节点，其中k是给定的正整数。例如，如果给定的链表是10->20->30->40->50->60，k为4，则应将列表修改为50->60->10->20->30->40。假设k小于链表中的节点数。

方法1：

为了旋转链表，我们需要将第k个节点的下一节点更改为NULL，将最后一个节点的下一节点更改为原头节点，最后将头指向第(k+1)个节点。因此，我们需要获取三个节点：第k个节点、第(k+1)个节点和最后一个节点。

从开头遍历列表并停在第k个节点。存储对第k个节点的指针。我们可以使用kthNode->next获取（k+1）th节点。继续遍历到末尾并存储指向最后一个节点的指针。最后，按上述更改指针。

// C++程序，逆时针旋转一个链表
#include <bits/stdc++.h>
using namespace std;
 
// 链表节点
class Node
{
    public:
    int data;
    Node* next;
};
 
// 该函数用于旋转一个链表
// 并更新头节点。该函数假设k的值
// 小于链表的长度。如果k大于或等于
// 链表长度，则不修改链表
void rotate(Node** head_ref, int k)
{
    if (k == 0)
        return;
 
    // 假设k=4，链表为10->20->30->40->50->60
    // 则当前节点会指向第k个节点或NULL
    Node* current = *head_ref;
    int count = 1;
    while (count < k && current != NULL)
    {
        current = current->next;
        count++;
    }
    // 如果当前节点为NULL，则k大于或等于链表的长度，不作修改
    if (current == NULL)
        return;
 
    // 存储当前节点，即第k个节点，存为kthNode
    Node* kthNode = current;
 
    // current 再遍历到链表尾部，即指向最后节点，即节点60
    while (current->next != NULL)
        current = current->next;
 
    // 将链表连成环，最后节点的next指向头节点，即节点10
    current->next = *head_ref;
 
    // 将第k+1个节点作为新头节点
    *head_ref = kthNode->next;
 
    // 断开连接第k个节点和第k-1个节点，即kthNode->next指向NULL
    kthNode->next = NULL;
}
 
// 工具函数：向链表中添加节点
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(void)
{
    // 创建一个空链表
    Node* head = NULL;
 
    // 创建一个链表为10->20->30->40->50->60
    for (int i = 60; i > 0; i -= 10)
        push(&head;, i);
 
    // 打印原链表
    cout << "Given linked list ";
    printList(head);
    rotate(&head;, 4);
 
    // 打印旋转后的链表
    cout << "Rotated Linked list ";
    printList(head);
 
    return (0);
}
// 本代码由rathbhupendra贡献```  

输出:

给定链表
10 20 30 40 50 60
旋转后的链表
50 60 10 20 30 40

时间复杂度：O(n) 其中n为链表中的节点数。代码只遍历了一次链表。

空间复杂度: O(1)

如果您发现任何不正确之处或者想分享更多讨论上述主题的信息，请留下评论。

方法2：

为将链表旋转k个节点，我们可以先将链表连成圆形，然后从头节点开始往前移动k-1个节点，将第k-1个节点的下一个节点指向NULL，并将第k个节点作为新的头节点。

// C++程序用于逆时针旋转链表
#include <bits/stdc++.h>
using namespace std;
 
// 链表节点
class Node
{
    public:
    int data;
    Node* next;
};
 
// 这个函数逆时针旋转链表并更新头。该函数假设k小于链表的大小。
void rotate(Node** head_ref, int k)
{
    if (k == 0)
        return;
 
    // 举个例子，k = 4且list = 10->20->30->40->50->60。
    Node* current = *head_ref;
 
    // 遍历到结尾。
    while (current->next != NULL)
        current = current->next;
 
    current->next = *head_ref;
    current = *head_ref;
 
    // 遍历链表到第k-1个位置，这将是旋转数组的最后一个元素。
    for (int i = 0; i < k - 1; i++)
        current = current->next;
 
    // 更新头部并将最后一个元素指针设置为NULL。
    *head_ref = current->next;
    current->next = NULL;
}
 
// 实用函数
// push一个节点
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(void)
{
    // 从空列表开始
    Node* head = NULL;
 
    // 创建列表
    // 10->20->30->40->50->60
    for (int i = 60; i > 0; i -= 10)
        push(&head, i);
 
    cout << "给定链表 ";
    printList(head);
    rotate(&head, 4);
 
    cout << "旋转后的链表 ";
    printList(head);
 
    return (0);
}
// 本代码由pkurada提供```  

输出结果:

给定链表 
10 20 30 40 50 60 
旋转后的链表 
50 60 10 20 30 40

时间复杂度：O(N) 其中N是给定链表中的节点数。

空间复杂度：O(1)