1.题目解析

2.讲解算法原理

解法:递归-> 重复的子问题

• 重复子问题 ->函数头的设计
  •  合并两个有序链表--->Node dfs(l1，l2)
• 只关心某一个子问题在做什么事情 ->函数体的设计
  • 比大小
  • l1→next = dfs( l1.next, l2)
  • return l1
• 递归的出口
  • if(l1==null)return l2

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) {
        ListNode head=dfs(list1,list2);
        return head;
    }
    public ListNode dfs(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        if(list1.val<=list2.val){
            list1.next= dfs(list1.next,list2);
            return list1;
        }else{
            list2.next= dfs(list1,list2.next);
            return list2;
        }
        
    }
}