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

import java.util.*;
public class Solution {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        //思路：遍历两个链表，保存，排序，输出
        if (pHead1 == null) return pHead2;
        if (pHead2 == null)return pHead1;
        if (pHead1 == null & pHead2 == null) return null;

        ArrayList<Integer> new_list = new ArrayList<>();  //定义一个新的list
        //遍历两个链表，存入list
	  	while (pHead1 != null) {
            new_list.add(pHead1.val);
            pHead1 = pHead1.next;
        }
        while (pHead2 != null) {
            new_list.add(pHead2.val);
            pHead2 = pHead2.next;
        }
	  	//排序
        Collections.sort(new_list);
		//把list转换成链表
        ListNode newnode = new ListNode(new_list.get(0));
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        for (int i = 0; i < new_list.size(); i++) {
            cur.next = new ListNode(new_list.get(i));
            cur = cur.next;
        }
        return dummyHead.next;

    }
}

第二种用递归

import java.util.*;
public class Solution {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
       if(pHead1 == null || pHead2 == null){
		 return pHead1 1= null? pHead1:pHead2;
	   }
	  if(pHead1.val < pHead2.val){
	  	pHead1.next = Merge(pHead1.next, pHead2);
		return pHead1;
	  }else{
	  pHead2.next = Merge(pHead1, pHead2.next);
	  return pHead2;
	  }
    }
}