image.png
    省空间的方法是修改链表指针，不引入新的链表节点。

    1.  public static void main(String[] args) {
    2.         ListNode node1 = new ListNode(1);
    3.         ListNode node2 = new ListNode(2);
    4.         ListNode node3 = new ListNode(4);
    5.         node1.next = node2;
    6.         node2.next = node3;
    8.         ListNode node11 = new ListNode(1);
    9.         ListNode node22= new ListNode(3);
    10.         ListNode node33 = new ListNode(4);
    11.         node11.next = node22;
    12.         node22.next = node33;
    14.         //ListNode head = mergeTwoLists2(node1, node11);
    15.         ListNode head2 = mergeTwoLists(node1, node11);
    18.     }
    19.     public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
    20.         if(l1 == null) return l2;
    21.         if(l2 == null) return l1;
    22.         ListNode cur1 = l1;
    23.         ListNode cur2 = l2;
    24.         ListNode head = new ListNode(-1);
    25.         ListNode tail = head;
    26.         while(cur1 !=null && cur2!=null){
    27.             if(cur1.val<cur2.val){
    28.                 tail.next = new ListNode(cur1.val);
    29.                 cur1 = cur1.next;
    30.             }else {
    31.                 tail.next = new ListNode(cur2.val);
    32.                 cur2 = cur2.next;
    33.             }
    34.             tail = tail.next;
    35.         }
    36.         if(cur1 == null){
    37.             tail.next = cur2;
    38.         }
    39.         else {
    40.             tail.next= cur1;
    41.         }
    42.         return head.next;
    44.     }
    45.     public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    46.         if(l1 == null) return l2;
    47.         if(l2 == null) return l1;
    48.         ListNode cur1 = l1.val <= l2.val? l1: l2;
    49.         ListNode cur2 = cur1 == l1 ?l2 : l1;
    50.         ListNode head = cur1;
    51.         ListNode pre= null;
    52.         ListNode next = cur1.next;
    53.         while(cur1!=null && cur2!=null){
    54.             if(cur1.val<= cur2.val){
    55.                 pre = cur1;
    56.                 cur1 = next;
    57.                 if(next != null){
    58.                     next = next.next;
    59.                 }
    60.             }
    61.             else {
    62.                 pre.next = cur2;
    63.                 cur2 = cur2.next;
    64.                 pre.next.next = cur1;
    65.                 pre = pre.next;
    66.                 ;
    67.             }
    68.         }
    69.         if(cur1 == null ){
    70.             pre.next = cur2;
    71.         }
    72.         return head;
    73.     }
    74.     public static class ListNode {
    75.         int val;
    76.         ListNode next;
    78.         ListNode(int x) {
    79.             val = x;
    80.         }
    81.     }