ตรวจสอบ Linked List เพิ่มขึ้นอย่างเคร่งครัดใน Python

ภาพรวม

โจทย์ตรวจสอบว่า singly linked list มีค่าเรียงเพิ่มขึ้นอย่างเคร่งครัด (strictly increasing) หรือไม่ คือค่าปัจจุบัน < ค่าถัดไป ทุกคู่

ตัวอย่าง

อินพุต: [2, 61, 105, 157]

2 < 61 < 105 < 157 → True

โค้ด Python (Recursive)

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

class Solution:
    def solve(self, head):
        if head.next is None:
            return True
        if head.val >= head.next.val:
            return False
        return self.solve(head.next)

ob = Solution()
head = make_list([2, 61, 105, 157])
print(ob.solve(head))

วิธี Iterative (แนะนำ ป้องกัน stack overflow)

def is_strictly_increasing(head):
    while head and head.next:
        if head.val >= head.next.val:
            return False
        head = head.next
    return True

ผลลัพธ์

True