一、题目

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

提示：

• 两个链表的节点数目范围是 [0, 50]

• -100 <= Node.val <= 100

• l1 和 l2 均按 非递减顺序 排列

二、提交记录

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        List<Integer> l1 = new ArrayList<>();

        ListNode node1 = list1;
        while (node1 != null) {
            l1.add(node1.val);
            node1 = node1.next;
        }

        List<Integer> l2 = new ArrayList<>();
        ListNode node2 = list2;
        while (node2 != null) {
            l2.add(node2.val);
            node2 = node2.next;
        }

        l1.addAll(l2);

        Collections.sort(l1, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        List<ListNode> list = new ArrayList<>();
        for (int i = 0; i < l1.size(); i++) {
            ListNode build = build(l1.get(i));
            list.add(build);
        }

        ListNode temp = null;
        ListNode ln1 = list.get(0);
        ListNode ln2 = list.get(1);

        temp = recursion(ln1, ln2, 1, list);

        return temp;
    }

    public static ListNode recursion(ListNode ln1, ListNode ln2, int i, List<ListNode> list) {
        ln1.next = ln2;
        i++;
        if (i < list.size()) {
            recursion(ln2, list.get(i), i, list);
        }
        return ln1;
    }

    public static ListNode build(int i) {
        return new ListNode(i);
    }
}