資料結構›Ch4 鏈結串列第 3 題／共 22 題
3. Linked List、遞迴
#DS-04-003易Linked List遞迴
Write a recursive function in pseudocode that takes a reference (or pointer) to the first node of a linked list as argument and returns the value of the maximum key in the list. Assume that the keys in the linked list are all positive integers. If the linked list is empty, the function should return 0.
參考答案與解析
FUNCTION MaxOfList(node):
IF node == NULL:
RETURN 0
restMax = MaxOfList(node.next)
IF node.key > restMax:
RETURN node.key
ELSE:
RETURN restMax
時間複雜度 O(n)，遞迴深度 O(n)（額外空間 O(n) 用於呼叫堆疊）。
📄 台大114
▤完整推導請見《WH 資工筆記 · 資料結構》Ch4 鏈結串列