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

给定一个双向链表，将该链表逆时针旋转N个节点，其中N是一个给定的正整数，且小于链表中节点的数目。

N=2

旋转后的链表：

举例：

输入： **a b c d e** N=2
输出： **c d e a b**

输入： **a b c d e f g h** N=4
输出： **e f g h a b c d**

为了旋转双向链表，我们需要改变第N个节点的next指针为NULL，最后一个节点的next指针为之前的头节点，头节点的prev指针指向最后一个节点，并将头节点指向第(N+1)个节点，新头节点的prev指针改为NULL(在双向链表中头节点的prev指针为NULL)。

因此我们需要获取三个节点的指针：第N个节点，第(N+1)个节点和最后一个节点。从链表开始遍历，直到到达第N个节点时停止遍历。存储Nth节点的指针。我们可以使用NthNode->next获取第（N+1）个节点。一直遍历直到末尾并存储最后一个节点的指针。最后，按照上述方式改变指针，最后使用PrintList函数打印旋转后的链表。

// C ++程序，通过N次逆时针旋转双向链接列表
//以将其逆时针旋转
#include <bits/stdc++.h>
using namespace std;
 
/*链接列表结构体*/
struct Node {
    char data;
    struct Node* prev;
    struct Node* next;
};
 
//此函数将双向链接列表逆时针旋转，并更新
//头。如果N大于等于大小，则该函数假定N是
//链表。如果N不大于或等于大小，则不修改列表
void rotate(struct Node** head_ref, int N)
{
    if(N == 0)
        return;
 
    //用N = 2和以下示例解释下面的代码
    //列表=a<->b<->c<->d<->e。
    struct Node* current = *head_ref;
 
    //此循环后，current要么指向第N个
    //要么指向空。在上面的示例中，current将指向节点“b”
    int count = 1;
    while(count < N && current != NULL) {
        current = current->next;
        count++;
    }
 
    //如果当前为NULL，则N大于或等于计数的节点数
    //在链表中。在这种情况下，不要更改列表
    if(current == NULL)
        return;
 
    //当前指向第N个节点。存储它在变量中。NthNode指向
    //上面的例子中的节点“b”
    struct Node* NthNode = current;
 
    //在此循环后，current将指向最后一个节点
    //在上面的示例中，current将指向节点“e”
    while(current->next != NULL)
        current = current->next;
 
    //将最后一个节点的下一个更改为前一个
    //头。现在，“e”的下一个已更改为节点“a”
    current->next = *head_ref;
 
    //将Head节点的前一个更改为当前
    //“a”的Prev现在更改为节点“e”
    (*head_ref)->prev = current;
 
    //将头更改为（N + 1）th节点
    //头现在更改为节点“c”
    *head_ref = NthNode->next;
 
    //将新头节点的前置更改为空
    //因为在双向链表中头节点的前面是NULL
    (*head_ref)->prev = NULL;
 
    //更改Nth节点的下一个到NULL
    //现在“b”的下一个为NULL
    NthNode->next = NULL;
}
 
//在双向链接列表的开头插入节点的函数
 void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node =  new Node;
    new_node->data = new_data;
    new_node->prev = NULL;
    new_node->next = (*head_ref);
    if((*head_ref) != NULL)
        (*head_ref)->prev = new_node;
   *head_ref = new_node;
}
 
/*打印链接列表的函数*/
void printList(struct Node* node)
{
    while(node->next != NULL) {
        cout << node->data << " "
             << "<=>"
             << " ";
        node = node->next;
    }
    cout << node->data;
}
 
//驱动器代码
int main(void)
{
    /*从空列表开始*/
    struct Node* head = NULL;
 
    /*让我们创建双重点的列表a<->b<->c<->d<->e */
    push(&head, 'e');
        push(&head, 'd');
    push(&head, 'c');
    push(&head, 'b');
    push(&head, 'a');
 
    int N = 2;
 
    cout << "给定链表
";
    printList(head);
    rotate(&head, N);
 
    cout << "
旋转后的链表
";
    printList(head);
 
    return 0;
}  

输出:

给定链表
a  b  c  d  e
旋转后的链表
c  d  e  a  b

时间复杂度: O（N）（N是链表节点的数量）

辅助空间: O（N）