这题前一阵子就看到了，一直没时间做，昨晚睡前想了想，要求n*log(n)以内的时间复杂度，第一时间想到的就是归并、快排和希尔排序（注：希尔排序时间为O(n^1.3)，在数据量大于2的情况下小于n*log(n)），个人以为，链表的特性更适合归并，所以采用归并排序，实现的merge代码如下：

public static ListNode merge(ListNode rhead, ListNode lhead) {        ListNode head = null;        if (rhead.val <= lhead.val) {            head = rhead;            rhead = rhead.next;        }        else {            head = lhead;            lhead = lhead.next;        }        ListNode node = head;        while(rhead != null || lhead != null){             if (rhead == null) {                node.next = lhead;                lhead = lhead.next;              }             else if (lhead == null) {                 node.next = rhead;                 rhead = rhead.next;             }             else if (rhead.val <= lhead.val) {                 node.next = rhead;                 rhead = rhead.next;             }             else {                 node.next = lhead;                 lhead = lhead.next;             }             node = node.next;        }        return head;    }

　　while中开始写为

if (rhead == null ||rhead.val <= lhead.val))  {...}else(..) {...}

　　报NullPoint异常，问题在于：|| 会判断每一个条件，如果rhead = null,那么rhead.val 错误；

　　然而这段代码在提交LeetCode时候报错：timeout, 修改while下代码：

while(rhead != null && lhead != null){            if (rhead.val > lhead.val) {               node.next = lhead;               lhead = lhead.next;             }            else if (lhead.val >= rhead.val) {                node.next = rhead;                rhead = rhead.next;            }            node = node.next;        }        if (rhead == null) {            while(lhead != null) {                node.next = lhead;                lhead = lhead.next;                node = node.next;                }        }        else if (lhead == null) {            while(rhead != null) {                node.next = rhead;                rhead = rhead.next;                node = node.next;            }        }

　　代码没有之前简洁，但是一下子就accepted.

　　但是对于这个问题一直耿耿于怀，然后google了下，给他跪了：time out is server's problem...

　　再次提交前面代码，果然通过AC……

　　但是对比下时间，后面的代码用时432ms,前面的代码用时476ms,除去每次运行的差异，个人认为，还一部分原因是：前面代码while每次都需要判断两个链表是否为null, 此处存在一定的时间开销，后面代码在一个链表为空以后，另一个链表只需不断迭代到为空。