头歌递归求解单链表中的最大值
时间: 2024-06-12 16:10:54 浏览: 12
好的,这是一个经典的链表问题。我们可以使用递归来解决它。具体思路是,将链表分为头节点和剩余节点两部分,然后递归求解剩余节点中的最大值,最后将头节点的值与剩余节点的最大值进行比较,返回较大值即可。
下面是代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def max_in_linked_list(head: ListNode) -> int:
if not head:
return float('-inf')
return max(head.val, max_in_linked_list(head.next))
```
其中,`float('-inf')` 表示负无穷大。
相关问题
//递归求解单链表中整数最大值 int maxList(LinkList L) { /********** Begin **********/ /********** End **********/ }
递归求解单链表中整数最大值的函数可以按照以下方式实现:
```cpp
int maxList(LinkList L) {
// 如果链表为空,返回一个较小的值作为最大值
if (L == NULL) {
return INT_MIN;
}
// 递归求解剩余链表的最大值
int maxRest = maxList(L->next);
// 返回当前节点值和剩余链表最大值中的较大值
return max(L->data, maxRest);
}
```
这个函数首先判断链表是否为空,如果为空则返回一个较小的值(这里使用INT_MIN)作为最大值。然后,递归调用函数求解剩余链表的最大值,并将结果保存在变量`maxRest`中。最后,返回当前节点值和剩余链表最大值中的较大值作为整个链表的最大值。
编写一个程序exp5-2.py,用递归求解单链表中倒数第K个结点.
好的,下面是exp5-2.py的代码:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def findKthToTail(head, k):
if not head or k == 0:
return None
fast = head
slow = head
for i in range(k):
if not fast:
return None
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow
# 测试代码
if __name__ == '__main__':
# 创建单链表 1 -> 2 -> 3 -> 4 -> 5 -> 6
head = ListNode(1)
p = head
for i in range(2, 7):
node = ListNode(i)
p.next = node
p = p.next
# 测试用例
print(findKthToTail(head, 0)) # None
print(findKthToTail(head, 1).val) # 6
print(findKthToTail(head, 3).val) # 4
print(findKthToTail(head, 6).val) # 1
print(findKthToTail(head, 7)) # None
```
该程序使用了双指针法,其中一个指针先走k步,然后两个指针同时往后走,当先走的指针到达链表末尾时,后走的指针就指向了倒数第k个节点。如果遍历完整个链表,先走的指针仍然没有到达末尾,那么就说明k大于链表长度,返回None。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)