利用Java怎么合并递增排序链表

这期内容当中小编将会给大家带来有关利用Java怎么合并递增排序链表,文章内容丰富且以专业的角度为大家分析和叙述,阅读完这篇文章希望大家可以有所收获。

前郭网站制作公司哪家好,找成都创新互联公司!从网页设计、网站建设、微信开发、APP开发、自适应网站建设等网站项目制作,到程序开发,运营维护。成都创新互联公司于2013年成立到现在10年的时间,我们拥有了丰富的建站经验和运维经验,来保证我们的工作的顺利进行。专注于网站建设就选成都创新互联公司

题目描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

解答:

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

简化一下,用那个三目运算符:

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

据说这道题面试的时候经常考,因为它跟斐波那契数列问题一样有递归和非递归两种解法,上面说了递归的解法,下面再来讲下非递归的解法:

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

上述就是小编为大家分享的利用Java怎么合并递增排序链表了,如果刚好有类似的疑惑,不妨参照上述分析进行理解。如果想知道更多相关知识,欢迎关注创新互联行业资讯频道。


当前标题:利用Java怎么合并递增排序链表
新闻来源:http://myzitong.com/article/gpsspc.html