题目：将两个有序链表合并为一个新链表。该新链表必须是之前两个链表的节点合并而成。

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4Output: 1->1->2->3->4->4

的做法

采用递归的方法，思路简洁，实现简单，每次比较返回较小值

public class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if(l1 == null){ return l2; } if(l2 == null){ return l1; } ListNode mergeHead; if(l1.val < l2.val){ mergeHead = l1; mergeHead.next = mergeTwoLists(l1.next, l2); } else{ mergeHead = l2; mergeHead.next = mergeTwoLists(l1, l2.next); } return mergeHead; } } 我的做法（实现复杂，提交了三次才通过）

class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

ListNode maxPointer = l1;

ListNode minPointer = l2;

ListNode maxHead = l1;

ListNode minHead = l2;

if (minPointer == null)

return maxPointer;

if (maxPointer == null)

return minPointer;

if (l1.val <= l2.val) {

minPointer = l1;

maxPointer = l2;

maxHead = l2;

minHead = l1;

}

ListNode head = minHead;

while (minPointer != null && maxPointer != null) {

while ((minPointer.next != null) && (minPointer.next.val > maxPointer.val)) {

maxHead = maxPointer.next;

minHead = minPointer.next;

minPointer.next = maxPointer;

maxPointer.next = minHead;

minPointer = maxPointer;

if (maxHead != null)

maxPointer = maxHead;

else

return head;

}

if (minPointer.next != null)

minPointer = minPointer.next;

else

while (maxPointer != null) {

minPointer.next = maxPointer;

minPointer = minPointer.next;

maxPointer = maxPointer.next;

}

}

return head;

}

}