บทนำ
การหมุน (rotate) Doubly Linked List จำนวน N โหนด คือการย้าย N โหนดแรกไปไว้ท้ายลิสต์ (left rotation) หรือย้าย N โหนดท้ายไปไว้หน้า (right rotation) ตัวอย่างนี้ทำ left rotation
โค้ดตัวอย่าง
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:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.size += 1
def display(self):
curr = self.head
while curr:
print(curr.data, end=' ')
curr = curr.next
print()
def rotate_left(self, k):
"""หมุนซ้าย k โหนด (ย้าย k ตัวแรกไปท้าย)"""
if k <= 0 or k >= self.size or self.head is None:
return
# หาโหนดที่ k (0-indexed: k-1)
curr = self.head
for _ in range(k - 1):
curr = curr.next
# curr คือโหนดสุดท้ายของส่วนที่จะย้าย
new_head = curr.next
# ปรับ pointer
self.tail.next = self.head
self.head.prev = self.tail
self.head = new_head
self.head.prev = None
self.tail = curr
self.tail.next = None
# ทดสอบ
dll = DoublyLinkedList()
for v in [10, 24, 54, 77, 24, 0]:
dll.append(v)
print("ก่อนหมุน:", end=' ')
dll.display()
dll.rotate_left(4)
print("หลังหมุนซ้าย 4:", end=' ')
dll.display()
ผลลัพธ์
ก่อนหมุน: 10 24 54 77 24 0 หลังหมุนซ้าย 4: 24 0 10 24 54 77
คำอธิบาย
- ตรวจสอบ edge cases: k <= 0, k >= size, empty list
- เดินหาโหนดที่ k-1 (โหนดสุดท้ายของส่วนหน้า)
new_head = curr.nextโหนดแรกของส่วนท้าย- เชื่อม tail เดิม → head เดิม (วนกลับ)
- ตั้ง head ใหม่ = new_head, tail ใหม่ = curr
- ตัด pointer เก่าทิ้ง (prev ของ head ใหม่, next ของ tail ใหม่)
Right Rotation
def rotate_right(self, k):
k = k % self.size
self.rotate_left(self.size - k)
