C++怎么旋转链表

在C++中，旋转链表是一个常见的操作，尤其是在处理链表数据结构时。旋转链表通常指的是将链表中的元素向右或向左移动k个位置。本文将详细介绍如何在C++中实现链表的旋转操作，并提供相应的代码示例。

1. 链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表可以分为单向链表、双向链表和循环链表等类型。在本文中，我们主要讨论单向链表的旋转操作。

1.1 单向链表的定义

在C++中，单向链表可以定义如下：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

其中，val表示节点的值，next是指向下一个节点的指针。

2. 链表旋转的基本思路

旋转链表的基本思路是将链表中的元素向右或向左移动k个位置。具体来说，向右旋转k个位置意味着将链表的最后k个节点移动到链表的前面。例如，给定链表 1->2->3->4->5，向右旋转2个位置后，链表变为 4->5->1->2->3。

2.1 旋转链表的步骤

1. 计算链表的长度：首先需要计算链表的长度，以便确定旋转的位置。
2. 找到旋转点：根据旋转的位置k，找到链表中第 n - k 个节点，其中n是链表的长度。
3. 断开链表：将链表从旋转点断开，分为两个部分。
4. 重新连接链表：将断开后的链表重新连接，形成旋转后的链表。

3. 实现链表旋转的C++代码

下面是一个完整的C++代码示例，展示了如何实现链表的旋转操作。

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) {
            return head;
        }

        // 计算链表的长度
        int length = 1;
        ListNode* tail = head;
        while (tail->next) {
            tail = tail->next;
            length++;
        }

        // 计算实际需要旋转的步数
        k = k % length;
        if (k == 0) {
            return head;
        }

        // 找到旋转点
        ListNode* newTail = head;
        for (int i = 0; i < length - k - 1; i++) {
            newTail = newTail->next;
        }

        // 断开链表并重新连接
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;
        tail->next = head;

        return newHead;
    }
};

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* current = head;
    while (current) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

// 辅助函数：创建链表
ListNode* createList(int n) {
    ListNode* head = new ListNode(1);
    ListNode* current = head;
    for (int i = 2; i <= n; i++) {
        current->next = new ListNode(i);
        current = current->next;
    }
    return head;
}

int main() {
    Solution solution;
    ListNode* head = createList(5);
    std::cout << "Original List: ";
    printList(head);

    int k = 2;
    ListNode* rotatedHead = solution.rotateRight(head, k);
    std::cout << "Rotated List (k=" << k << "): ";
    printList(rotatedHead);

    return 0;
}

3.1 代码解析

1. 计算链表的长度：通过遍历链表，计算链表的长度length，并找到链表的尾节点tail。
2. 计算实际需要旋转的步数：由于旋转k个位置可能大于链表的长度，因此需要对k取模，得到实际需要旋转的步数。
3. 找到旋转点：通过遍历链表，找到第 n - k 个节点newTail，即旋转点。
4. 断开链表并重新连接：将链表从旋转点断开，将后半部分链表连接到前半部分的前面，形成旋转后的链表。

3.2 示例输出

运行上述代码，输出如下：

Original List: 1 2 3 4 5 
Rotated List (k=2): 4 5 1 2 3 

4. 时间复杂度分析

• 计算链表长度：需要遍历整个链表，时间复杂度为O(n)。
• 找到旋转点：需要遍历链表的前 n - k 个节点，时间复杂度为O(n - k)。
• 断开并重新连接链表：操作的时间复杂度为O(1)。

因此，整个旋转操作的时间复杂度为O(n)，其中n是链表的长度。

5. 总结

本文详细介绍了如何在C++中实现链表的旋转操作。通过计算链表的长度、找到旋转点、断开链表并重新连接，可以高效地完成链表的旋转操作。希望本文的内容能够帮助你更好地理解和掌握链表旋转的实现方法。