21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路

自己原来的思路是这样的：两层while循环，外层遍历l1，内层遍历l2，
将l1的各个元素插入到l2中，其中涉及到l1链表的拆开和l2链表的合并，写出一堆bug...
去网上查这道题的思路，发现思路有两种比较好的方法：
递归法：不好理解，看的有点懵
双指针法：比较容易理解，实现起来也比较容易,如图：


h1,h2遍历链表的每一个节点，比较两个val,只要是小的一方就创建新节点加到head后面,相等的的情况，创建两个节点，h1,h2各自右移一位。
如果遇到还有链表没右结束，则直接将没有结束的那些接到ptr指针后头，这样就合并到head链表了。

代码

class Solution {
   
     public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
   
		
		//真实返回的链表头节点
        ListNode head = new ListNode(-1);
        head.next = null;
        //辅助指针
        ListNode ptr =head;

		//l1,l2的辅助指针
        ListNode h1 = l1;
        ListNode h2 = l2;

        while(h1 != null && h2 != null){
   
        //开始比较两个链表的元素大小
        	if(h1.val < h2.val){
   
        	//小的创建新节点并且接到ptr后头
        		ListNode node =  new ListNode(h1.val);
        		node.next = null;
        		ptr.next = node;

        		ptr = node;
				
				//移动小的一头
        		h1 = h1.next;
        	}else if(h1.val > h2.val){
   
        	//小的创建新节点并且接到ptr后头
        		ListNode node =  new ListNode(h2.val);
        		node.next = null;
        		ptr.next = node;

                ptr = node;
				//移动小的一头
        		h2 = h2.next;
            }else{
   
            	ListNode node1 =  new ListNode(h1.val);
            	ListNode node2 =  new ListNode(h2.val);

            	node1.next = null;
        		ptr.next = node1;
        		ptr = node1;

        		node2.next = null;
        		ptr.next = node2;
        		ptr = node2;
				
				//移动两边
                h1 = h1.next;
        		h2 = h2.next;
            }      
    }

//如果有一遍还有元素，则接到ptr的后面
    if(h1!=null){
   
    	ptr.next = h1;
    }
    if(h2!=null){
   
    	ptr.next = h2;
    }

    return head.next;
     }

}

测试