左旋与右旋在链表中的实现

概述

链表是一种常见的数据结构，广泛应用于各种算法和程序设计中。对于链表操作来说，左旋（Left Rotate）和右旋（Right Rotate）是两种重要的操作方式。通过这两种旋转操作，可以改变链表元素的排列顺序，实现一些高级的数据处理需求。本文将详细介绍如何在单向链表和双向链表中实现这两种旋转操作。

单向链表中的左旋与右旋

左旋（Left Rotate）

定义

左旋是指将链表中的所有节点依次向左移动一个位置，最左边的节点移动到最右边。具体地说，就是取原链表的第一个节点作为新的头结点，并将剩余部分连接起来。

实现步骤

找到链表的尾部：遍历链表直到最后一个元素。
更新链表尾部和头部的指针：
- 记录下当前头结点（即第一个节点）。
- 将原链表的尾部指向头结点的下一个节点。
- 更新新的头结点为原来记录的第一个节点，并将其 next 指向空。

示例代码

def left_rotate(head):
    if not head or not head.next:
        return head
    
    # 找到尾部并重新连接
    tail = head
    while tail.next:
        tail = tail.next

    new_head = head.next  # 新的头结点
    tail.next = head      # 将原链表的最后一个节点指向旧头结点
    head.next = None      # 原头结点变为尾结点，断开与后面的连接
    
    return new_head

右旋（Right Rotate）

定义

右旋是指将链表中的所有节点依次向右移动一个位置，最右边的节点移动到最左边。具体地说，就是取原链表的第一个节点作为新的尾结点，并将剩余部分连接起来。

实现步骤

找到链表的头部：直接使用当前头结点。
更新链表头部和尾部的指针：
- 记录下当前尾结点（即最后一个节点）。
- 将原链表的第一个元素的 next 指向空，断开与后面的连接。
- 更新新的尾结点为原来记录的头结点，并将其 next 指向原尾结点。

示例代码

def right_rotate(head):
    if not head or not head.next:
        return head
    
    # 重新构建链表
    tail = head
    while tail.next.next:
        tail = tail.next

    new_tail = tail.next       # 新的尾节点
    new_tail.next = head       # 将新的尾结点指向原头结点
    tail.next = None           # 原最后一个节点变成新头部，断开与后面的连接
    
    return new_tail

双向链表中的左旋与右旋

左旋（Left Rotate）

在双向链表中实现左旋与单向链表相似，主要区别在于需要更新前后节点的指针。

实现步骤

找到尾部并重新连接：
- 从头结点开始遍历直到最后一个元素。
- 更新当前头结点（即第一个节点）与其前驱的 next 指针为 None。
- 新头结点将指向原链表的尾部，同时调整其前驱指针。

示例代码

def left_rotate(head):
    if not head or not head.next:
        return head
    
    # 重新构建双向链表
    tail = head
    while tail.next:
        tail = tail.next

    new_head = head.next     # 新的头结点
    head.prev.next = None    # 更新原尾部节点，断开与后面的连接
    tail.next = head         # 将新的尾结点指向旧头结点
    head.prev = tail         # 旧头部更新前驱指针为新尾部
    
    return new_head

右旋（Right Rotate）

在双向链表中实现右旋与单向链表也类似，但需考虑前后节点的连接。

实现步骤

找到头部并重新构建：
- 从头结点开始遍历直到第一个元素。
- 更新当前尾结点（即最后一个节点）与其后继的 next 指针为 None。
- 新尾结点将指向原链表的第一个，同时调整其后继指针。

示例代码

def right_rotate(head):
    if not head or not head.next:
        return head
    
    # 重新构建双向链表
    tail = head
    while tail.next:
        tail = tail.next

    new_tail = head     # 新的尾节点
    head.prev.next = None   # 更新原头部节点，断开与前面的连接
    tail.next = head         # 将新的头部指向旧尾部
    tail.prev = None          # 旧尾部更新前驱指针为None
    
    return new_tail

结语

通过对链表进行左旋和右旋操作，可以有效地改变链表内节点的顺序。掌握这些基本操作不仅能够帮助我们更好地理解和处理复杂的数据结构问题，还能在实际编程中提供更多的灵活性和效率。无论是单向还是双向链表，只要合理地调整指针关系，即可实现所需的旋转效果。