21. Merge Two Sorted Lists -- dummy node / Amazon LinkedIn Apple Microsoft

https://leetcode.com/problems/merge-two-sorted-lists/

九章答案： make so much sense .但是对于dummy的使用还是要多体会的。第二遍明白了

http://www.jiuzhang.com/solutions/merge-two-sorted-lists/

方法一： Iteratively

public class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

ListNode dummy = new ListNode(0);

// dummy.next = l1;

ListNode lastNode = dummy;

while (l1 != null && l2 != null) {

if (l1.val < l2.val) {

lastNode.next = l1;

l1 = l1.next;

}

else {

lastNode.next = l2;

l2 = l2.next;

}

lastNode = lastNode.next;

}

if (l1 != null) {

lastNode.next = l1;

}

if (l2 != null) {

lastNode.next = l2;

}

return dummy.next;

}

}

解释参考博客：

http://www.cnblogs.com/springfor/p/3862040.html

更聪明的方法，但是会有stack over flow when the two lists are too long.

https://discuss.leetcode.com/topic/2513/a-recursive-solution/5

方法二： Recursively

public class Solution {

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

if (l1 == null) return l2;

if (l2 == null) return l1;

if (l1.val < l2.val) {

l1.next = mergeTwoLists(l1.next, l2);

return l1;

}

else {

l2.next = mergeTwoLists(l2.next, l1);

return l2;

}

}

}