[数据结构与算法]剑指Offer算法题——合并两个排序的链表

题目描述：

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

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

方法：递归

思路：该题涉及到链表，我们不难想到要使用指针l1和l2和头结点来进行遍历。.

????????用于两个链表都是递增的，我们不需要考虑那么多，只需关注l1.val和l2.val的大小关系，来进行节点添加顺序的指定。

? ? ? ? 引入头结点是因为：用于初始状态合并链表中无节点，因此循坏第一轮时无法将节点添加到合并链表中。

算法：

1.先设置一个头结点dummy，放到新链表前，最后返回的就是dummy.next；设置cur为当前节点，从dummy开始

2.当两个链表都非空时进入循环，令新链表的下一个节点cur.next为val更小的节点，相应的链

表节点后移一位

3.每次循环记得cur也要后移一位

4.如果循环结束后还有链表非空，cur指向非空链表

5.返回dummy.next

代码：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1 : l2;
        return dummy.next;
    }