Chương trình sắp xếp linked list xen kẽ đầu cuối trong Python

Cho linked list đơn. Sắp xếp lại theo thứ tự: node cuối, node đầu, node倒数 thứ 2, node thứ 2, ...

Ví dụ

Đầu vào: 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9

Đầu ra: 9 → 1 → 8 → 2 → 7 → 3 → 6 → 4 → 5

Thuật toán (Mảng trung gian)

1. Duyệt linked list, lưu tất cả giá trị vào list vals.
2. Duyệt lại linked list, lần lượt gán giá trị từ vals.pop() (cuối) và vals.pop(0) (đầu) xen kẽ.

Triển khai Python

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

def make_list(elements):
    head = ListNode(elements[0])
    for val in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(val)
    return head

def print_list(head):
    ptr = head
    print('[', end='')
    while ptr:
        print(ptr.val, end=', ')
        ptr = ptr.next
    print(']')

class Solution:
    def solve(self, node):
        # Bước 1: thu thập giá trị
        vals = []
        cur = node
        while cur:
            vals.append(cur.val)
            cur = cur.next
        
        # Bước 2: ghi đè giá trị xen kẽ đầu-cuối
        cur = node
        while cur and vals:
            cur.val = vals.pop()      # Lấy từ cuối
            cur = cur.next
            if not cur:
                break
            cur.val = vals.pop(0)     # Lấy từ đầu
            cur = cur.next
        return node

# Test
ob = Solution()
head = make_list([1,2,3,4,5,6,7,8,9])
print_list(ob.solve(head))
# Output: [9, 1, 8, 2, 7, 3, 6, 4, 5, ]

Độ phức tạp

• Thời gian: O(n²) do pop(0) O(n). Có thể dùng deque để O(n).
• Không gian: O(n) cho mảng giá trị.

Phiên bản tối ưu O(n) với deque

from collections import deque

class Solution:
    def solve(self, node):
        vals = deque()
        cur = node
        while cur:
            vals.append(cur.val)
            cur = cur.next
        
        cur = node
        toggle = True  # True: pop right, False: pop left
        while cur and vals:
            cur.val = vals.pop() if toggle else vals.popleft()
            cur = cur.next
            toggle = not toggle
        return node