2つの順序付きチェーンテーブルを再帰的にマージ

再帰:プログラム呼び出し自体のプログラミングテクニックを再帰と呼ぶ.
一般に、再帰には境界条件、再帰前進セグメント、再帰帰還セグメントが必要である.境界条件が満たされない場合、再帰的に前進する.境界条件が満たされると、再帰的に返されます.
再帰終了条件
再帰の終了条件は一般的に再帰関数の内部で定義され、再帰呼び出し前に条件判断を行い、判断の結果に基づいて自身を呼び出し続けるか、returnを選択する.再帰の終了を返します.終了の条件:1、再帰の回数がある制限値に達したか否かを判断する.2、演算の結果がある範囲に達したか否かを判断するなど、設計の目的に応じて選択する.
2つの順序付きチェーンテーブルを新しい順序付きチェーンテーブルに結合して返します.新しいチェーンテーブルは、指定された2つのチェーンテーブルのすべてのノードを接合することによって構成されます.
例:
入力:1->2->4、1->3->4出力:1->1->2->3->4->4
 
この問題は再帰的に実現することができ、新しいチェーンテーブルも新しいノードを構築する必要はありません.以下に再帰的な3つの要素の終了条件を列挙します.2つのチェーンテーブルはそれぞれl 1とl 2と呼ばれ、l 1が空またはl 2が空の場合、戻り値を終了します.各層の呼び出しは順序付けられたチェーンテーブルのヘッダレベルの再帰内容を返します.l 1のval値がもっと小さい場合、l 1.nextは並べ替えられたチェーンヘッダに接し,l 2同理O(m+n)O(m+n)O(m+n),mmmはl 1の長さ,nnnはl 2の長さである
  

/**
 * Definition for singly-linked list.
 * public class ListNode { //      
 *     int val; //  
 *     ListNode next; //          
 *     ListNode(int x) {  //        ，   val 
 *        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) {
      // mergeTwoLists(l1, l2.next);
      //    l1    l2    ，  l1               l2，         
            l1.next = mergeTwoLists(l1.next, l2);
            //  l1      l1     
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}