So implementieren Sie die Zusammenführung verknüpfter Listen mit inkrementeller Sortierung in Java

Dieser Artikel stellt hauptsächlich die Java-Programmierung vor, um die Zusammenführung aufsteigend sortierter verknüpfter Listen zu implementieren, zwei Methoden, und der Code wird mit allen geteilt, damit Freunde in Not darauf verweisen können.

Problembeschreibung

Geben Sie zwei monoton ansteigende verknüpfte Listen ein und geben Sie die kombinierte verknüpfte Liste der beiden verknüpften Listen aus. Natürlich benötigen wir die kombinierte verknüpfte Liste Liste, um die Minusregel zu erfüllen.

Antwort:

/* 
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; 
  } 
}

Verwenden Sie zur Vereinfachung den ternären Operator:

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;
	}
}

Es wird gesagt, dass diese Frage oft in Interviews getestet wird, da es zwei Lösungen gibt, eine rekursive und eine nicht rekursive, wie das Fibonacci-Sequenzproblem. Die rekursive Lösung ist oben erwähnt Folgendes ist: Lassen Sie uns über die nicht rekursive Lösung sprechen:

/* 
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 tmp1 = list1;
		ListNode tmp2 = list2;
		ListNode head = new ListNode(0);
		//这里不能把返回链表赋值为null，因为下一行马上就要把它赋值给另一链表，得让它在内存里有位置才行 
		ListNode headptr = head;
		while(tmp1 != null && tmp2!=null){
			if(tmp1.val <= tmp2.val) 
			          {
				head.next=tmp1;
				head = head.next;
				tmp1 = tmp1.next;
			} else{
				head.next=tmp2;
				head = head.next;
				tmp2=tmp2.next;
			}
		}
		//其中一个链表已经跑到头之后，继续单链表的合并 
		while(tmp1 != null){
			head.next = tmp1;
			head = head.next;
			tmp1= tmp1.next;
		}
		while(tmp2 != null){
			head.next = tmp2;
			head = head.next;
			tmp2= tmp2.next;
		}
		head = headptr.next;
		return head;
	}
}

Zusammenfassung

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Zusammenführung verknüpfter Listen mit inkrementeller Sortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!