Java编程实现递增排序链表的合并

时间:2022-12-08 12:48:13

题目描述

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

解答:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
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;
  }
}

 

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

?
1
2
3
4
5
6
7
8
9
10
11
12
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;
    }
}

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/*
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编程实现递增排序链表的合并的全部内容,如有不足之处,欢迎留言指出,希望对大家有所帮助。感谢朋友们对本站的支持!

原文链接:http://blog.csdn.net/qq_15062527/article/details/48863153