链接两个有序链表

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

[java] view plain copy

/**

* Definition for singly-linked list.

* public class ListNode {

*     public int val;

*     public ListNode next;

*     public ListNode(int x) { val = x; }

* }

*/

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, 这是一个在分布式系统中比较有用的基本操作，还是需要重视，面试中可以发散出很多问题。