java归并两个无序链表并排序_Java代码归并两个已排好序的链表

题目是：归并两个已排好序的链表，假设链表是从小到大递增排序的

算法思路就是：我的解法就是重新建立一个新的链表，将归并好的存放进去，一共有三种情况，假设俩个链表为链表l1和链表l2

1、第一种情况就是l1和l2同时不为空

2、l1为空，l2不为空

3、l1不为空，l2为空

针对第一种情况，还存在两中考虑，如果1的值小于2的值则将1的值存入新建链表内，如果2的值小于1的值则将2的值存入到新建链表内

针对第2种情况，新建的链表就是对链表2的复制

针对第三种情况，新建的链表就是对链表1的复制

该方法的优点就是时间短但是耗费的空间多。

具体代码如下：

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */ public class Solution {     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {         ListNode newNode=new ListNode(0);         ListNode p=newNode;         while(l1!=null&&l2!=null){             if(l1.val