LeetCode Java刷题笔记—21. 合并两个有序链表_(2)创建两个单链表pa和pb,再编写一个函数将两个非空单链表a(头指针为pa)和b(头指

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

使用指针或者递归可解，其中指针方式更加容易理解，通过一个哨兵节点来连接两个链表的节点。如果采用递归，实际上下面案例中两种递归的思想是一的，只不过递归2的写法更简单而已。

1 方式一 指针

/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * 简单
 */
public class LeetCode21{

   /**
    * 指针
    *
    * @param list1
    * @param list2
    * @return
    */
   public ListNode mergeTwoLists( ListNode list1, ListNode list2 ){
      //通过一个哨兵节点来连接两个链表的节点
      ListNode dummy = new ListNode( 0 );
      ListNode pre = dummy;
      while( list1 != null && list2 != null ){
         //比较大小，谁更小，那么谁就是成为pre的后继，并且更新该引用的指向
         if( list1.val >= list2.val ){
            pre.next = list2;
            list2 = list2.next;
         }
         else{
            pre.next = list1;
            list1 = list1.next;
         }
         //更新pre的指向
         pre = pre.next;
      }
      //需要注意剩下还未追加的部分节点
      pre.next = list1 == null ? list2 : list1;
      return dummy.next;
   }

   public class ListNode{

      int val;
      ListNode next;

      ListNode(){

      }

      ListNode( int val ){

         this.val = val;
      }

      ListNode( int val, ListNode next ){

         this.val = val;
         this.next = next;
      }
   }
}
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
47
48
49
50
51
52
53
54
55
56
57
58

2 方式二 递归一

/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * 简单
 */
public class LeetCode21{

   /**
    * 递归1
    *
    * @param list1
    * @param list2
    * @return
    */
   public ListNode mergeTwoLists1( ListNode list1, ListNode list2 ){

      if( list1 == null || list2 == null ){
         return list1 == null ? list2 : list1;
      }
      if( list1.val > list2.val ){
         //返回一个大于当前小节点的最小节点，成为当前小节点的后继
         list2.next = mergeTwoLists1( list1, list2.next );
         //返回小节点
         return list2;
      }
      else{
         //返回一个大于当前小节点的最小节点，成为当前小节点的后继
         list1.next = mergeTwoLists1( list1.next, list2 );
         //返回小节点
         return list1;
      }
   }


   public class ListNode{

      int val;
      ListNode next;

      ListNode(){

      }

      ListNode( int val ){

         this.val = val;
      }

      ListNode( int val, ListNode next ){

         this.val = val;
         this.next = next;
      }
   }
}
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
47
48
49
50
51
52
53
54
55
56

3 方式三 递归二

/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 * 简单
 */
public class LeetCode21{

   /**
    * 递归2
    * 可以看作是递归1的更加简略的版本，但它们的思想都是一样的
    *
    * @param list1
    * @param list2
    * @return
    */
   public ListNode mergeTwoLists2( ListNode list1, ListNode list2 ){

      if( list1 == null || list2 == null ){
         return list1 == null ? list2 : list1;
      }
      //获取较小的节点
      ListNode min = list1.val > list2.val ? list2 : list1;
      min.next = mergeTwoLists2( min.next, min == list1 ? list2 : list1 );
      //返回小节点
      return min;
   }

   public class ListNode{

      int val;
      ListNode next;

      ListNode(){

      }

      ListNode( int val ){

         this.val = val;
      }

      ListNode( int val, ListNode next ){

         this.val = val;
         this.next = next;
      }
   }
}
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
47
48
49