6-6 递归求单链表最大值 分数 10 全屏浏览题目 切换布局 作者 ds课程组 单位 临沂

题目描述

给定一个单链表的头节点 head，递归求这个单链表中的最大值。

示例

输入: 1->2->3->4->5->6->7
输出: 7

输入: 2->3->4->5->6->7->1
输出: 7

输入: 3->4->5->6->7->1->2
输出: 7

数据范围：

链表长度不超过 10000，链表中的元素取值范围为 [-10000, 10000]。

思路

对于单链表的递归操作，我们首先要明确的是，递归的终止条件是什么？

对于单链表来说，当我们递归到了最后一个节点，也就是 head == null 时，我们就可以停止递归操作，返回一个默认的最小值（这里是 -10000）。

然后我们需要明确的是，递归的过程中我们要做什么？

对于当前节点 head，我们需要递归求出后面的节点的最大值，并将其与当前节点的值进行比较，取其中的最大值。

最后我们将得到的最大值返回即可。

代码

C++ 代码

class ListNode {
public:
int val;
ListNode* next;
ListNode(int x): val(x), next(NULL) {}
};

int getMax(ListNode* head) {
if (!head) {
return -10000;
}
int nextMax = getMax(head->next);
return max(head->val, nextMax);
}

Java 代码

class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public int getMax(ListNode head) {
if (head == null) {
return -10000;
}
int nextMax = getMax(head.next);
return Math.max(head.val, nextMax);
}

Python 代码

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

def getMax(head: ListNode) -> int:
if not head:
return -10000
nextMax = getMax(head.next)
return max(head.val, nextMax)