螺旋矩阵 II：从理论到实践的五种算法解析

输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL

输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL
向右旋转 2 步: 1->2->0->NULL
向右旋转 3 步: 0->1->2->NULL
向右旋转 4 步: 2->0->1->NULL

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def rotateRight(head, k):
    """
    使用闭合环的方法进行链表旋转
    :param head: ListNode, 链表的头节点
    :param k: int, 旋转的位置数
    :return: ListNode, 旋转后的链表头节点
    """
    if not head or not head.next or k == 0:
        return head
    
    # 计算链表长度并形成环
    lastElement = head
    length = 1
    while lastElement.next:
        lastElement = lastElement.next
        length += 1
    lastElement.next = head
    
    # 找到新的尾部：（长度 - k % 长度 - 1）的位置
    k = k % length
    steps_to_new_tail = length - k
    new_tail = head
    for i in range(steps_to_new_tail - 1):
        new_tail = new_tail.next
    
    new_head = new_tail.next
    
    # 断开环
    new_tail.next = None
    
    return new_head
# 示例代码用于创建链表和打印链表
def create_list(lst):
    head = current = ListNode(lst[0])
    for number in lst[1:]:
        current.next = ListNode(number)
        current = current.next
    return head
def print_list(node):
    while node:
        print(node.val, end=" -> ")
        node = node.next
    print("NULL")
# 示例调用
lst = create_list([1, 2, 3, 4, 5])
rotated_lst = rotateRight(lst, 2)
print_list(rotated_lst)  # 输出: 4 -> 5 -> 1 -> 2 -> 3 -> NULL

def rotateRight(head, k):
    """
    使用数组模拟链表旋转
    :param head: ListNode, 链表的头节点
    :param k: int, 旋转的位置数
    :return: ListNode, 旋转后的链表头节点
    """
    if not head or not head.next or k == 0:
        return head
    
    # 转换链表到数组
    nodes = []
    current = head
    while current:
        nodes.append(current.val)
        current = current.next
    
    # 数组旋转
    k = k % len(nodes)
    nodes = nodes[-k:] + nodes[:-k]
    
    # 重建链表
    new_head = current = ListNode(nodes[0])
    for val in nodes[1:]:
        current.next = ListNode(val)
        current = current.next
    
    return new_head
# 示例调用
lst = create_list([1, 2, 3, 4, 5])
rotated_lst = rotateRight(lst, 2)
print_list(rotated_lst)  # 输出: 4 -> 5 -> 1 -> 2 -> 3 -> NULL

def rotateRight(head, k):
    """
    直接通过链表旋转实现
    :param head: ListNode, 链表的头节点
    :param k: int, 旋转的位置数
    :return: ListNode, 旋转后的链表头节点
    """
    if not head or not head.next or k == 0:
        return head
    
    # 计算长度并形成环
    old_tail = head
    length = 1
    while old_tail.next:
        old_tail = old_tail.next
        length += 1
    old_tail.next = head
    
    # 计算新尾部位置
    k = k % length
    new_tail = head
    for i in range(length - k - 1):
        new_tail = new_tail.next
    
    new_head = new_tail.next
    new_tail.next = None
    
    return new_head
# 示例调用
lst = create_list([1, 2, 3, 4, 5])
rotated_lst = rotateRight(lst, 2)
print_list(rotated_lst)  # 输出: 4 -> 5 -> 1 -> 2 -> 3 -> NULL

def rotateRight(head, k):
    """
    使用改进的数组模拟方法旋转链表
    :param head: ListNode, 链表的头节点
    :param k: int, 旋转的位置数
    :return: ListNode, 旋转后的链表头节点
    """
    if not head:
        return None
    
    # 转换链表到数组
    nodes = []
    while head:
        nodes.append(head)
        head = head.next
    
    k = k % len(nodes)
    nodes = nodes[-k:] + nodes[:-k]
    
    # 重建链表
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    nodes[-1].next = None
    
    return nodes[0]
# 示例调用
lst = create_list([1, 2, 3, 4, 5])
rotated_lst = rotateRight(lst, 2)
print_list(rotated_lst)  # 输出: 4 -> 5 -> 1 -> 2 -> 3 -> NULL

def rotateRight(head, k):
    """
    使用反向索引旋转链表
    :param head: ListNode, 链表的头节点
    :param k: int, 旋转的位置数
    :return: ListNode, 旋转后的链表头节点
    """
    if not head or not head.next or k == 0:
        return head
    
    # 完成一次完整遍历以确定长度并形成环
    last = head
    length = 1
    while last.next:
        last = last.next
        length += 1
    last.next = head
    
    # 确定新的头部和尾部
    k = k % length
    if k:
        for _ in range(length - k):
            last = last.next
    head = last.next
    last.next = None
    
    return head
# 示例调用
lst = create_list([1, 2, 3, 4, 5])
rotated_lst = rotateRight(lst, 2)
print_list(rotated_lst)  # 输出: 4 -> 5 -> 1 -> 2 -> 3 -> NULL