C++程序旋转双向链表N个节点

介绍

双向链表是一种非常常见的数据结构，它的每个节点都包含了一个指向前驱节点的指针和一个指向后继节点的指针。在一些应用中，我们需要对双向链表进行旋转操作。

本文将介绍如何使用C++实现旋转双向链表N个节点的方法。我们会先介绍如何创建和打印双向链表，然后展示如何进行旋转操作。

创建和打印双向链表

首先，我们需要定义一个双向链表节点的结构体。结构体包含三个成员变量：val表示节点的值，prev表示指向前驱节点的指针，next表示指向后继节点的指针。

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

接下来，我们提供一个函数createList用于创建长度为N的双向链表。

ListNode* createList(int N) {
    ListNode* head = new ListNode(1); // 头节点
    ListNode* tail = head;
    for (int i = 2; i <= N; ++i) {
        ListNode* node = new ListNode(i);
        tail->next = node;
        node->prev = tail;
        tail = tail->next;
    }
    return head;
}

函数createList的原理非常简单。我们首先创建1号节点作为头结点，接着循环创建2号到N号节点，每创建一个节点就将其连接到链表的尾部。

现在，我们将提供函数printList用于打印上述创建的双向链表。

void printList(ListNode* head) {
    ListNode* node = head;
    while (node != nullptr) {
        std::cout << node->val << ", ";
        node = node->next;
    }
    std::cout << std::endl;
}

函数printList的原理也非常简单。我们从头结点开始遍历整个链表，每遍历到一个节点就输出它的值。

我们可以使用以上两个函数建立一个长度为10的双向链表，并打印出来。

ListNode* head = createList(10);
printList(head);

输出结果如下：

1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

旋转双向链表

接下来，我们将介绍如何对上述双向链表进行旋转。

假设我们希望将链表向右旋转k步。

首先，我们需要找到最后一个节点。这个操作比较简单，我们只需要从头节点开始不断跳转next指针，直到指向的节点为nullptr即可。

ListNode* tail = head;
while (tail->next != nullptr) {
    tail = tail->next;
}

接下来，我们需要将尾部和头部连接起来。

tail->next = head;
head->prev = tail;

现在，我们已经将双向链表变成了一个环形链表。接着，我们需要找到需要断开的点。这个操作比较简单，我们只需要将k模链表长度得到的余数即可。

k = k % n;

其中n是链表长度。

最后，我们需要将找到的断点断开，并返回新的头节点。

ListNode* newTail = head;
for (int i = 0; i < n - k - 1; ++i) {
        newTail = newTail->next;
    }
    ListNode* newHead = newTail->next;
    newHead->prev = nullptr;
    newTail->next = nullptr;
    return newHead;

现在，我们将上述操作进行封装，定义函数rotateList，用于实现旋转双向链表的完整操作。

ListNode* rotateList(ListNode* head, int k) {
    if (head == nullptr) return head;

    int n = 1;
    ListNode* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
        ++n;
    }

    k = k % n;
    if (k == 0) return head;

    tail->next = head;
    head->prev = tail;

    ListNode* newTail = head;
    for (int i = 0; i < n - k - 1; ++i) {
        newTail = newTail->next;
    }
    ListNode* newHead = newTail->next;
    newHead->prev = nullptr;
    newTail->next = nullptr;
    return newHead;
}

现在，我们可以使用以上函数对上述创建的长度为10的双向链表进行测试。例如，我们旋转链表3步，如下所示：

ListNode* head = createList(10);
printList(head);
head = rotateList(head, 3);
printList(head);

输出结果如下：

1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
8, 9, 10, 1, 2, 3, 4, 5, 6, 7,

完整代码

下面是完整的C++程序代码：

#include <iostream>

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

ListNode* createList(int N) {
    ListNode* head = new ListNode(1); // 头节点
    ListNode* tail = head;
    for (int i = 2; i <= N; ++i) {
        ListNode* node = new ListNode(i);
        tail->next = node;
        node->prev = tail;
        tail = tail->next;
    }
    return head;
}

void printList(ListNode* head) {
    ListNode* node = head;
    while (node != nullptr) {
        std::cout << node->val << ", ";
        node = node->next;
    }
    std::cout << std::endl;
}

ListNode* rotateList(ListNode* head, int k) {
    if (head == nullptr) return head;

    int n = 1;
    ListNode* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
        ++n;
    }

    k = k % n;
    if (k == 0) return head;

    tail->next = head;
    head->prev = tail;

    ListNode* newTail = head;
    for (int i = 0; i < n - k - 1; ++i) {
        newTail = newTail->next;
    }
    ListNode* newHead = newTail->next;
    newHead->prev = nullptr;
    newTail->next = nullptr;
    return newHead;
}

int main() {

    ListNode* head = createList(10);
    printList(head);

    head = rotateList(head, 3);
    printList(head);

    return 0;
}