LeetCode：归并两个有序的链表 (递归) (java)

我会带着你远行 2023-07-16 11:57 16阅读 0赞

# 题目描述 #

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

**示例**：

**输入**：1->2->4, 1->3->4  
**输出**：1->1->2->3->4->4

**原题链接：**[link][].

# 代码 #

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
    class Solution { 
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) { 
        if(l1==null) return l2;
        if(l2==null) return l1;
        if(l1.val>l2.val){ 
            l2.next=mergeTwoLists(l1,l2.next);，
            return l2;
        }else{ 
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }
      }
    }

# 思路 #

#### 1.先设置嵌套出口 ####

当极端情况下：l1为空，返回l2；l2为空，返回l1。

if(l1==null) return l2;
     if(l2==null) return l1;

#### 2.再设置嵌套入口 ####

若l1.val>l2.val，那么l2是所需要的结点，故,  
l2.next=mergeTwoLists(l1,l2.next)。

if(l1.val>l2.val){
            l2.next=mergeTwoLists(l1,l2.next);
            //return l2;
        }else{
            l1.next=mergeTwoLists(l1.next,l2);
            //return l1;
        }

#### 3.大问题化小问题 ####

若l1.val>l2.val，那么l2是所需要的结点。故, return l2。  
若l2.val>l1.val，那么l1是所需要的结点，故, return l1。

if(l1.val>l2.val){
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }

[link]: https://leetcode-cn.com/problems/merge-two-sorted-lists/