Python程序：将双向链表旋转n个节点

双向链表是一种常用的数据结构，其中每个节点都有一个前驱节点和一个后继节点，可以实现前后遍历，而且插入、删除操作比单链表方便。本文将介绍如何利用Python程序将双向链表旋转n个节点。

更多Python相关文章，请阅读：Python 教程

双向链表的定义

在开始之前，我们先来定义一下双向链表的结构体：

typedef struct DListNode {
    int val;
    struct DListNode *prev;
    struct DListNode *next;
} DListNode;

其中，val表示节点的值，prev指向前驱节点，next指向后继节点。有了这个结构体，我们就可以定义一个双向链表了：

typedef struct DoubleLinkedList {
    DListNode *head;
    DListNode *tail;
} DoubleLinkedList;

其中，head指向双向链表的头节点，tail指向双向链表的尾节点。

双向链表的创建

在双向链表中插入一个节点，需要考虑两个方向：前驱方向和后继方向。因此，我们先来定义一个函数，用于在头部插入节点：

void addToHead(DoubleLinkedList *list, int val) {
    DListNode *node = (DListNode *) malloc(sizeof(DListNode));
    node->val = val;
    node->prev = NULL;
    node->next = list->head;
    if (list->head != NULL) {
        list->head->prev = node;
    }
    list->head = node;
    if (list->tail == NULL) {
        list->tail = node;
    }
}

其中，首先申请一个新的节点，然后将节点值赋为val，前驱节点设为NULL，后继节点为当前链表头，并将当前链表的头指针指向该节点。如果当前链表的尾指针为NULL，说明表中还没有节点，此时将尾指针也指向该节点。

为了方便测试，我们可以再定义一个函数，用于打印双向链表中的所有节点：

void printList(DoubleLinkedList *list) {
    DListNode *ptr = list->head;
    while (ptr != NULL) {
        printf("%d ", ptr->val);
        ptr = ptr->next;
    }
    printf("\n");
}

双向链表的旋转

在双向链表中，我们可以通过前驱和后继指针互相访问节点。因此，对于要旋转的节点个数n，我们只需要找到链表的尾指针，将其指向当前链表的头指针，并将当前链表的头指针指向原头节点的后继节点即可。这个过程可以利用如下函数实现：

def rotateList(node:ListNode, k:int)->ListNode:
    if node==None or k==0:
        return node
    last = node
    cnt = 1
    while last.next!=None:
        cnt += 1
        last = last.next
    k %= cnt
    if k == 0:
        return node
    while cnt>k:
        node = node.next
        cnt -= 1
    last.next = head
    head = node.next
    node.next = None
    return head

其中，node指向双向链表的头节点，k表示要旋转的节点个数。首先，我们计算出当前链表的长度cnt，然后将k对cnt取余，以简化代码的复杂度。如果取余后结果为0，说明链表不用旋转，直接返回即可。接下来，我们需要找到旋转后的链表头节点位置，即距离链表头节点k个节点的后继节点。最后，则需要将链表的头指针指向该节点的后继节点，将链表的尾指针指向原链表的头节点，并将该节点的后继节点设为None。

示例代码

下面是一个完整的Python程序，用于创建一个双向链表并实现旋转功能：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.prev = None
        self.next = None

def createList(arr):
    head = ListNode(0)
    tail = head
    for val in arr:
        node = ListNode(val)
        node.prev = tail
        tail.next = node
        tail = node
    return head.next

def printList(node:ListNode):
    while node!=None:
        print(node.val, end=" ")
        node = node.next
    print()

def rotateList(node:ListNode, k:int)->ListNode:
    if node==None or k==0:
        return node
    last = node
    cnt = 1
    while last.next!=None:
        cnt += 1
        last = last.next
    k %= cnt
    if k == 0:
        return node
    while cnt>k:
        node = node.next
        cnt -= 1
    last.next = head
    head = node.next
    node.next = None
    return head

arr = [1,2,3,4,5]
head = createList(arr)
printList(head)
head = rotateList(head, 2)
printList(head)

运行结果为：