21. Merge Two Sorted Lists

,

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode pre = dummyHead;

        ListNode nodeA = list1, nodeB = list2;
        while (nodeA != null && nodeB != null) {
            if (nodeA.val <= nodeB.val) {
                pre.next = nodeA;
                nodeA = nodeA.next;
            } else {
                pre.next = nodeB;
                nodeB = nodeB.next;
            }

            pre = pre.next;
        }

        pre.next = nodeA != null ? nodeA : nodeB;
        return dummyHead.next;
    }
}

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        } else {
            if (list1.val <= list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list2.next, list1);   
                return list2;             
            }
        } 
    }
}

References

21. Merge Two Sorted Lists
剑指 Offer 25. 合并两个排序的链表