JZ25 合并两个排序的链表

解法一 定义一个额外的链表和一个指针,移动指针,将数据插入到新的链表中

public class Solution {
          
   
    public ListNode Merge(ListNode list1,ListNode list2) {
          
   
        //一个已经为空了，直接返回另一个
        if(list1 == null) 
            return list2;
        if(list2 == null)
            return list1;
        //加一个表头
        ListNode head = new ListNode(0); 
        ListNode cur = head;
        //两个链表都要不为空
        while(list1 != null && list2 != null){
          
    
            //取较小值的节点
            if(list1.val <= list2.val){
          
    
                cur.next = list1;
                //只移动取值的指针
                list1 = list1.next; 
            }else{
          
   
                cur.next = list2;
                //只移动取值的指针
                list2 = list2.next; 
            }
            //指针后移
            cur = cur.next; 
        }
        //哪个链表还有剩，直接连在后面
        if(list1 != null) 
            cur.next = list1;
        else
            cur.next = list2;
        //返回值去掉表头
        return head.next; 
    }
}

解法二 借助arraylist数组,将两个链表的值存入,然后排顺,在放入其中一个链表中返回

public static ListNode Merge(ListNode list1,ListNode list2) {
          
   
        if(list1 == null && list2 == null)
            return null;
        ArrayList<Integer> list = new ArrayList<Integer>();
        ArrayList<ListNode> result = new ArrayList<ListNode>();
        while (list1 != null) {
          
   
            list.add(list1.val);
            list1 = list1.next;
        }
        while (list2 != null) {
          
   
            list.add(list2.val);
            list2 = list2.next;
        }
        Collections.sort(list);
        for(int i = 0;i<list.size();i++){
          
   
            ListNode temp = new ListNode(list.get(i));
            result.add(temp);
        }
        for(int i = 0;i<result.size()-1;i++){
          
   
            result.get(i).next = result.get(i+1);
        }
        return result.get(0);
    }