1ms Java Solution with clear explanation

• Hard to explain in words, just see the below diagram:

Two lists are:

1->3->4->6
2->5->7->8

Cause 1<2, so pick current list be (1)->3->4->6, other list to be (2)->5->7->8 (note that the current node is enclosed by '()').

``````1) 1<2, current list: 1->(3)->4->6, other list: (2)->5->7->8
2) 3>2, current list: 1->2->(5)->7->8, other list: (3)->4->6
4) 5>3, current list: 1->2->3->(4)->6, other list: (5)->7->8
6) 4<5, current list: 1->2->3->4->(6), other list: (5)->7->8
7) 6>5, current list: 1->2->3->4->5->(7)->8, other list: (6)
8) 7>6, current list: 1->2->3->4->5->6->(), other list: (7)->8
9) combine current list with other list: 1->2->3->4->5->6->7->8
``````

Note that for current list, we need to keep two references: pre and curr

`````` public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null)
return l2;
if(l2==null)
return l1;
ListNode head = l1.val<=l2.val ? l1 : l2;
ListNode pre = head;  // previous node of final list
ListNode curr = pre.next;  // current node of final list
ListNode other = l1==head ? l2 : l1;  // list other than head
while(curr!=null) {
if(curr.val<=other.val) {
pre = curr;
curr = curr.next;
} else {
pre.next = other;
pre = other;
other = curr;
curr = pre.next;
}
}
pre.next = other;