สมมติมี Linked List ต้องเขียน 2 ฟังก์ชันเช็คว่าเรียงจากมากไปน้อย (Non-increasing) แบบ Iterative และ Recursive
เช่น Input L = [15, 13, 8, 6, 4, 2] Output True
ขั้นตอนแก้:
- Iterative: วนลูปเช็ค current.val > current.next.val ทุกคู่
- Recursive: Base case head หรือ head.next เป็น None -> True; Return head.val > head.next.val AND solve_rec(head.next)
ตัวอย่างโค้ด
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
def solve_iter(head):
if head == None:
return True
while head.next != None:
current = head
if current.val <= current.next.val:
return False
head = head.next
return True
def solve_rec(head):
if head == None or head.next == None:
return True
return head.val > head.next.val and solve_rec(head.next)
L = make_list([15, 13, 8, 6, 4, 2])
print(solve_iter(L))
print(solve_rec(L))
Input
[15, 13, 8, 6, 4, 2]
Output
True True
