Java でインクリメンタルソートリンクリストマージを実装する方法

この記事では主に、昇順ソート済みリンク リストのマージを実現するための Java プログラミング、2 つの方法を紹介します。コードは、必要な友人が参照できるように全員と共有されます。

問題の説明

2 つの単調増加リンク リストを入力し、2 つのリンク リストを結合したリンク リストを出力します。もちろん、単調非減少規則を満たす結合されたリンク リストが必要です。

答え:

/* 
public class ListNode { 
  int val; 
  ListNode next = null; 
 
  ListNode(int val) { 
    this.val = val; 
  } 
}*/ 
public class Solution { 
  public ListNode Merge(ListNode list1,ListNode list2) { 
    if(list1==null)return list2; //判断到某个链表为空就返回另一个链表。如果两个链表都为空呢？没关系，这时候随便返回哪个链表，不也是空的吗? 
    if(list2==null)return list1; 
    ListNode list0=null;//定义一个链表作为返回值 
    if(list1.val<list2.val){//判断此时的值，如果list1比较小，就先把list1赋值给list0，反之亦然 
      list0=list1; 
      list0.next=Merge(list1.next, list2);//做递归，求链表的下一跳的值 
      } 
      else{ 
      list0=list2; 
      list0.next=Merge(list1, list2.next); 
      } 
 return list0; 
  } 
}

三項演算子を使って簡略化してください:

public class Solution {
	public ListNode Merge(ListNode list1,ListNode list2) {
		if(list1==null) 
		      return list2;
		if(list2==null) 
		      return list1;
		ListNode head;
		list0= list1.val>list2.val?list2:list1;
		list0.next = list1.val>list2.val?Merge(list1,list2.next):Merge(list1.next,list2);
		return list0;
	}
}

この質問はフィボナッチ数列の質問と同じなので、面接でよくテストされると言われています再帰的解決策と非再帰的解決策の 2 つがあります。再帰的解決策については、以下で説明します。

以上がJava でインクリメンタルソートリンクリストマージを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。