递归之合并两个有序链表"/>
宏观角度认识递归之合并两个有序链表
21. 合并两个有序链表 - 力扣(LeetCode)
依旧是利用宏观角度来看待问题,其中最主要的就是要找到重复的子问题;
题目中要求把两个有序链表进行合并,同时不能够创建新的节点,并返回链表的起始点:因此可以思考它的解题过程,首先比较两个链表的首节点,提取出较小的一个,然后将剩下的两个链表继续进行合并,并对提取出的较小的那个进行返回;
1. 重复子问题 -> 函数头:总会有两个链表进行合并,因此要给出两个链表的头结点位置,并要有一个返回值;
2. 解析子问题 -> 函数体:两个链表的头结点进行比较,提取出较小的那个,继续调用链表合并方法,将较小的那个节点进行返回;
3. 递归出口:当两个链表中的某一个链表的指向结点为空的时候,说明这个链表已经遍历完了,就直接返回另一个链表的指向节点;
代码实现
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {// 递归出口if(list1 == null) return list2;if(list2 == null) return list1;if(list1.val <= list2.val){// 提取出当前的最小数,并指向后续的链表合并中list1.next = mergeTwoLists(list1.next,list2);return list1; }else{// 提取出当前的最小数,并指向后续的链表合并中list2.next = mergeTwoLists(list1,list2.next);return list2;}}
}
此处再对于递归和深度搜索进行一个分析,实际上递归的展开图,很大程度上就是对一棵树进行一个深度优先遍历。而递归的重点,就是要找到题目当中的重复子问题;
更多推荐
宏观角度认识递归之合并两个有序链表
发布评论