LeetCode Java刷题笔记—21. 合并两个有序链表

21. 合并两个有序链表

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

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

• 1 方式一 指针
• 2 方式二 递归一
• 3 方式三 递归二

public class LeetCode21{

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

public class LeetCode21{

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

public class LeetCode21{

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