lettcode第21题： 合并两个有序链表

这到题目是简单，解决办法就是迭代或者递归。

递归其实就是循环的另一种实现方式啦，比如写循环，我们可以使用for循环，或者while或者do..while实现，思想都是一样的。

方法一：循环

 // 使用迭代
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;

        while (list1 != null || list2 != null){
            if (list1 == null){
                node.next = new ListNode(list2.val);
                list2 = list2.next;
            } else if (list2 == null){
                node.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                if (list1.val <= list2.val){
                    node.next = new ListNode(list1.val);
                    list1 = list1.next;
                } else {
                    node.next = new ListNode(list2.val);
                    list2 = list2.next;
                }
            }
            node = node.next;
        }
        return dummy.next;
    }

方法二：递归

 // 使用递归
    public ListNode recursion(ListNode list1, ListNode list2){
        if (list1 == null){
            return list2;
        }

        if (list2 == null){
            return list1;
        }

        if (list1.val < list2.val){
            list1.next = recursion(list1.next, list2);
            return list1;
        } else {
            list2.next = recursion(list1, list2.next);
            return list2;
        }
    }

完整的代码，测试用例。

import java.util.List;


public class Solution {

    public static void main(String[] args) {    
        Solution solution = new Solution();
        ListNode l1 = new ListNode(1, new ListNode(2 ,new ListNode(4)));
        ListNode l2 = new ListNode(1, new ListNode(3 ,new ListNode(4)));
        // solution.mergeTwoLists(l1, l2).print();
        solution.recursion(l1, l2).print();
    }

    // 使用迭代
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode node = dummy;

        while (list1 != null || list2 != null){
            if (list1 == null){
                node.next = new ListNode(list2.val);
                list2 = list2.next;
            } else if (list2 == null){
                node.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                if (list1.val <= list2.val){
                    node.next = new ListNode(list1.val);
                    list1 = list1.next;
                } else {
                    node.next = new ListNode(list2.val);
                    list2 = list2.next;
                }
            }
            node = node.next;
        }
        return dummy.next;
    }

    // 使用递归
    public ListNode recursion(ListNode list1, ListNode list2){
        if (list1 == null){
            return list2;
        }

        if (list2 == null){
            return list1;
        }

        if (list1.val < list2.val){
            list1.next = recursion(list1.next, list2);
            return list1;
        } else {
            list2.next = recursion(list1, list2.next);
            return list2;
        }
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    public void print(){
        System.out.print(this.val + " ");
        if (this.next != null){
            this.next.print();
        }
    }
}