Maison > Java > javaDidacticiel > Comment implémenter la fusion de listes chaînées de tri incrémentiel en Java

Comment implémenter la fusion de listes chaînées de tri incrémentiel en Java

黄舟
Libérer: 2017-10-17 09:46:22
original
2056 Les gens l'ont consulté

Cet article présente principalement la programmation Java pour implémenter la fusion de listes chaînées triées par ordre croissant, deux méthodes, et le code est partagé avec tout le monde pour référence par les amis dans le besoin.

Description du problème

Entrez deux listes chaînées croissantes de manière monotone et affichez la liste chaînée combinée des deux listes chaînées. Bien sûr, nous avons besoin de la liste chaînée combinée. liste pour satisfaire la monotonie.

Réponse :


/* 
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; 
  } 
}
Copier après la connexion

Pour simplifier, utilisez l'opérateur ternaire :


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;
	}
}
Copier après la connexion

On dit que cette question est souvent testée lors des entretiens, car elle a deux solutions, récursive et non récursive, comme le problème de la séquence de Fibonacci. La solution récursive est mentionnée ci-dessus, et ce qui suit est Parlons de la solution non récursive :


/* 
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;
	}
}
Copier après la connexion

Résumé

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Derniers numéros
Impossible d'installer Java
Depuis 1970-01-01 08:00:00
0
0
0
Java peut-il être utilisé comme backend du Web ?
Depuis 1970-01-01 08:00:00
0
0
0
Installer JAVA
Depuis 1970-01-01 08:00:00
0
0
0
Aide : Données chiffrées JAVA Décryptage PHP
Depuis 1970-01-01 08:00:00
0
0
0
Est-ce en langage Java ?
Depuis 1970-01-01 08:00:00
0
0
0
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal