Obviously a recursive solution is ok, however it use a lot of stack memory dealing such as "1->10->11->12" and "2->3->4->5->6->13->14->15".

My solution is to reduce stack use while inserting a "constant list" with the "big list" into the "small list".

Suppose p.val < q.val, then we should find a "constant list" in q that

p.val < q.val < ..... < q.somenext.val < p.next < q.somenext.next.val

We always do the same things, finally we can make it.

Poor English, don't mind : )

```
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) return null;
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode res;
if (l1.val < l2.val) {
res = l1;
merge(l1, l2);
} else {
res = l2;
merge(l2, l1);
}
return res;
}
public void merge(ListNode small, ListNode big) {
ListNode p = small;
ListNode q = big;
// Node p is smaller than q now
// Get the proper p.next whose val is bigger than q
while (p.next != null && p.next.val < q.val) p = p.next;
if (p.next == null) {
p.next = q;
return;
}
// temp = q
// p -> p.next
// temp -> .... -> q-> q.next
// p -> temp-> ......-> q -> p.next -> q.next
ListNode temp = q;
while (q.next != null && q.next.val < p.next.val) q = q.next;
if (q.next == null) {
q.next = p.next;
p.next = temp;
return;
} else {
ListNode pNode = p.next;
ListNode qNode = q.next;
q.next = p.next;
p.next = temp;
merge(pNode, qNode);
}
}
```