Leetcode:21-合并两个有序链表

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;
     }

}

测试