Python - Xoay Doubly Linked List N nút

Xoay (rotate) Doubly Linked List: dịch chuyển các node sao cho node tại vị trí N trở thành head mới, các node trước đó chuyển về cuối.

Ví dụ: List 10 <-> 24 <-> 54 <-> 77 <-> 24 <-> 0, xoay 4 nút -> 24 <-> 0 <-> 10 <-> 24 <-> 54 <-> 77

Triển khai

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
    
    def append(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = self.tail = new_node
        else:
            new_node.prev = self.tail
            self.tail.next = new_node
            self.tail = new_node
        self.size += 1
    
    def rotate(self, n):
        """
        Xoay list sang trái n vị trí.
        Node tại vị trí n (1-based) trở thành head mới.
        """
        if n <= 0 or n >= self.size or self.size <= 1:
            return  # Không xoay hoặc không hợp lệ
        
        # Tìm node tại vị trí n (sẽ thành tail mới)
        current = self.head
        for _ in range(n - 1):
            current = current.next
        
        new_tail = current
        new_head = current.next
        
        # Nối tail cũ với head cũ (tạo vòng tạm)
        self.tail.next = self.head
        self.head.prev = self.tail
        
        # Cập nhật head, tail
        self.head = new_head
        self.head.prev = None
        
        self.tail = new_tail
        self.tail.next = None
    
    def display(self):
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" <-> ".join(elements) if elements else "Empty")

# Demo
dll = DoublyLinkedList()
for val in [10, 24, 54, 77, 24, 0]:
    dll.append(val)

print("Danh sách gốc:")
dll.display()

print("\nXoay 4 nút:")
dll.rotate(4)
dll.display()

print("\nXoay thêm 2 nút:")
dll.rotate(2)
dll.display()

Kết quả

Danh sách gốc:
10 <-> 24 <-> 54 <-> 77 <-> 24 <-> 0

Xoay 4 nút:
24 <-> 0 <-> 10 <-> 24 <-> 54 <-> 77

Xoay thêm 2 nút:
54 <-> 77 <-> 24 <-> 0 <-> 10 <-> 24

Giải thích

• Tìm node tại vị trí n (1-based) -> sẽ thành new_tail.
• Node sau nó (new_tail.next) -> thành new_head.
• Nối tail.next = head và head.prev = tail tạo vòng tròn tạm.
• Cập nhật head, tail, cắt vòng bằng head.prev = None, tail.next = None.

Xoay phải (rotate right)

def rotate_right(self, n):
    """Xoay sang phải n vị trí (tương đương xoay trái size-n)."""
    n = n % self.size
    if n == 0:
        return
    self.rotate(self.size - n)

# Test
dll = DoublyLinkedList()
for v in [1, 2, 3, 4, 5]:
    dll.append(v)
dll.display()      # 1 <-> 2 <-> 3 <-> 4 <-> 5
dll.rotate_right(2)
dll.display()      # 4 <-> 5 <-> 1 <-> 2 <-> 3

Xoay bằng cách tách và nối (không tạo vòng)

def rotate_v2(self, n):
    if n <= 0 or n >= self.size:
        return
    
    # Tách tại vị trí n
    current = self.head
    for _ in range(n - 1):
        current = current.next
    
    new_head = current.next
    new_tail = current
    
    # Phần sau n
    new_head.prev = None
    # Phần trước n
    new_tail.next = None
    
    # Nối phần sau lên trước
    self.tail.next = self.head
    self.head.prev = self.tail
    
    self.head = new_head
    self.tail = new_tail

Độ phức tạp

• Thời gian: O(n) - phải duyệt đến vị trí n.
• Không gian: O(1) - chỉ đổi con trỏ.