Merge Two Sorted Lists -- LeetCode

原题链接: http://oj.leetcode.com/problems/merge-two-sorted-lists/
这道题目比较简单，经典的链表基本操作。维护两个指针对应两个链表，因为一般会以一条链表为基准，比如说l1, 那么如果l1当期那的元素比较小，那么直接移动l1即可，否则将l2当前的元素插入到l1当前元素的前面。算法时间复杂度是O(m+n),m和n分别是两条链表的长度，空间复杂度是O(1)，代码如下：

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode helper = new ListNode(0);
    ListNode pre = helper;
    helper.next = l1;
    while(l1!=null && l2 != null)
    {
        if(l1.val>l2.val)
        {
            ListNode next = l2.next;
            l2.next = pre.next;
            pre.next = l2;
            l2 = next;
        }
        else
        {
            l1 = l1.next;
        }
        pre = pre.next;

    }
    if(l2!=null)
    {
        pre.next = l2;
    }
    return helper.next;
}

这个题类似的有Merge Sorted Array，只是后者是对数组进行合并操作，面试中可能会一起问到。扩展题目Merge k Sorted Lists, 这是一个在分布式系统中比较有用的基本操作，还是需要重视，面试中可以发散出很多问题。