Kiểm tra danh sách liên kết đã sắp xếp (Iterative & Recursive) - Python

Bài toán: Cho danh sách liên kết đơn, kiểm tra xem nó có sắp xếp giảm dần (non-increasing) hay không. Triển khai cả hai cách: lặp và đệ quy.

Cấu trúc Node

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

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

Phương pháp lặp (Iterative)

def solve_iter(head):
    if head is None:
        return True
    while head.next is not None:
        if head.val <= head.next.val:  # non-increasing: current >= next
            return False
        head = head.next
    return True

Phương pháp đệ quy (Recursive)

def solve_rec(head):
    if head is None or head.next is None:
        return True
    return head.val > head.next.val and solve_rec(head.next)

Test

L = make_list([15, 13, 8, 6, 4, 2])
print(solve_iter(L))  # True
print(solve_rec(L))   # True

L2 = make_list([1, 3, 2])
print(solve_iter(L2)) # False

Kết quả

True
True

Giải thích

• Iterative: Duyệt qua list, kiểm tra current.val > next.val tại mỗi bước. O(n) time, O(1) space.
• Recursive: Điều kiện dừng: list rỗng hoặc 1 phần tử → True. Bước đệ quy: kiểm tra cặp hiện tại VÀ đệ quy phần còn lại. O(n) time, O(n) call stack.
• Yêu cầu: non-increasing (giảm dần, cho phép bằng nhau? Code dùng > nghiêm ngặt, nên strictly decreasing).