合并两个排序的链表

图解：

思路：

1.创建一个虚的头结点

2，将两个链表的头结点的值进行比较大小

3.将小的节点连接到新形成的链表中

4.更新值小的头结点，将其向后移动一位

5.重复这个过程直到有表为空，那么就将没有比较过大小的片段进行拼接

方法一：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        //设置虚的头结点，放在合并后形成的新表的最前面
         ListNode dummynode=new ListNode(-1);
         ListNode cur=dummynode;
         //循环的条件：两个表都非空
         while(pHead1!=null&& pHead2!=null){
            //执行的语句：将两个表头的值的大小进行比较，将较小的插入新的表中，更新对应的头节点
               if(pHead1.val<=pHead2.val){
                     cur.next=pHead1;
                     pHead1=pHead1.next;
               }else{
                     cur.next=pHead2;
                     pHead2=pHead2.next;
               }
               //更新cur的值
               cur=cur.next;
         }
         //当有表变为空后，将未比较的区间进行连接（哪个表的头节点非空，就将这个表的节点连接到新的表中）
         if(pHead1==null){
            cur.next=pHead2;
         }else{
            cur.next=pHead1;
         }
         return dummynode.next;
    }
}

方法二：（递归）

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        //设置虚的头结点，放在合并后形成的新表的最前面
         ListNode dummynode=new ListNode(-1);
         ListNode cur=dummynode;
         //循环的条件：两个表都非空
         while(pHead1!=null&& pHead2!=null){
            //执行的语句：将两个表头的值的大小进行比较，将较小的插入新的表中，更新对应的头节点
               if(pHead1.val<=pHead2.val){
                     cur.next=pHead1;
                     pHead1=pHead1.next;
               }else{
                     cur.next=pHead2;
                     pHead2=pHead2.next;
               }
               //更新cur的值
               cur=cur.next;
         }
         //当有表变为空后，将未比较的区间进行连接（哪个表的头节点非空，就将这个表的节点连接到新的表中）
         if(pHead1==null){
            cur.next=pHead2;
         }else{
            cur.next=pHead1;
         }
         return dummynode.next;
    }
}