题解 | #合并两个有序的链表#

记录自己的解题思路

解法一，刚做过有序数组的题，所以直接参考合并有序数组的算法，新建一个链表和一个哨兵节点（因为有去无回，需要哨兵节点来记录头节点的位置），遍历两个有序链表list1和list2，因为需要升序，那么谁小取谁做新链表的下一个节点，取谁的节点就往后移位，直到尾部null。

  public ListNode Merge(ListNode list1,ListNode list2) {

         if(list1==null){
             return list2;
         }

         if(list2==null){
             return list1;
         }
         ListNode result = new ListNode(-1);
         ListNode guard = result;//哨兵节点，很重要
         while(true){
             if(list1 == null && list2 == null){//全部取完了，可以结束了。
                 break;
             }
             if(list1==null){//list1取完了，后面的全部取list2的。
                 result.next = list2;
                 list2 = list2.next;
                 result = result.next;
             }else if(list2 == null){//list2取完了，后面全部取list1的。
                 result.next = list1;
                 list1 = list1.next;
                 result = result.next;
             }else if(list1.val<=list2.val){//和数组一样，谁小取谁的
                 result.next = list1;
                 list1 = list1.next;
                 result = result.next;
             }else if(list1.val>list2.val){//和数组一样，谁小取谁的
                 result.next = list2;
                 list2 = list2.next;
                 result = result.next;
             }
         }
         return guard.next;
     }

解法二，对解法一进行优化，观察到，如果想用尽一个链表，那么直接指向它的头节点就行了，省去解法一中，取剩余节点的步骤。

    public ListNode Merge(ListNode list1,ListNode list2) {

        if(list1==null){
            return list2;
        }

        if(list2==null){
            return list1;
        }
        ListNode result = new ListNode(-1);
        ListNode guard = result;
        while(list1!=null && list2!=null){

            if(list1.val<=list2.val){//同解法一
                result.next = list1;
                list1 = list1.next;
                result = result.next;
            }else if(list1.val>list2.val){//同解法一
                result.next = list2;
                list2 = list2.next;
                result = result.next;
            }
        }

        if(list1==null){//优化点，剩下的节点全部取list2
            result.next = list2;
        }

        if(list2==null){//优化点，剩下的节点全部取list1
            result.next = list1;
        }
        return guard.next;
    }
}

解法三， 使用递归，虽然想到了，但是半天没有写对，最后参考题解后才做出来，思想是：每次都取list1和list2的头节点进行比较，谁小谁当头节点，然后继续往后比较，这个步骤每一步都是一样的，写递归就是特别zhu'y。

    public ListNode Merge(ListNode list1,ListNode list2) {

        //退出条件
        if(list1==null){
            return list2;
        }
        //退出条件
        if(list2==null){
            return list1;
        }

        ListNode guard = null;
        //谁小谁当头结点，然后继续重复这个步骤
        if(list1.val>=list2.val){
            guard = list2;
            guard.next = Merge(list1,list2.next);

        }else{
            guard = list1;
            guard.next = Merge(list1.next,list2);

        }
        return guard;
    }