LeetCode-Merge Two Sorted List

原创：悦乐书 程序员小川

合并两个已排序的链表并将其作为新链表返回。 新链表应该通过拼接前两个链表的节点来完成。例如：

链表L1包含三个节点，为1,2,4

链表L2包含三个节点，为1,3,4

将L1和L2合并后的新链表包含6个节点，为1,1,2,3,4,4

分析

先来看段代码，下面是定义的ListNode类，有两个属性，一个是存储整数值的val，一个是ListNode类本身的next，存储下一个ListNode的地址值（指针）。形象的解释就是，链表可以是拉链的齿轮，互相咬合；也可以是电影《盗梦空间》中的梦中梦；就像大盒子里面可以继续放盒子一样。

public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}

为了更好的理解链表是怎么存储值的，且看下面的代码。l1的next属性引用了l2，l2的next属性引用了l3。

public class Easy_21_MergeTwoSortedList {
    public static void main(String[] args) {
        Easy_21_MergeTwoSortedList instance = new Easy_21_MergeTwoSortedList();
        ListNode l1 = new ListNode(1);
        ListNode l2 =new ListNode(2);
        ListNode l3 =new ListNode(4);
        l1.next = l2;
        l2.next = l3;   
        System.out.println(instance.listNodeToString(l1));
        ListNode l4 = new ListNode(1);
        ListNode l5 =new ListNode(3);
        ListNode l6 =new ListNode(4);
        l4.next = l5;
        l5.next = l6;
        System.out.println(instance.listNodeToString(l4));
    }

    public String listNodeToString(ListNode L){
        List<Integer> list = new ArrayList<Integer>();
        while(L != null){
            list.add(L.val);
            L = L.next;
        }
        return list.toString();
    }
}

解法

因为给的链表都是已经排过序的（由小到大），只需要依次比较两个链表的元素val值即可，并且存入一个新的链表里面。如果某一个链表先循环完，新链表剩下的元素就是另外一个链表剩下的元素。

 public static ListNode mergeTwoList(ListNode l1,ListNode l2){
        ListNode dumy = new ListNode(-1);
        ListNode cur= dumy;
        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 dumy.next;
    }