LeetCode Note Java 00021：Merge Two Sorted Lists

將輸入的兩個有序 Linked List 合併後返回，返回的 Linked List 也需是有序。

題目

Merge Two Sorted Lists Easy

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

我的解法

/**
 * 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) {
        ListNode outputHead = new ListNode();// 一個假頭，Linked List 常使用這方式來避免尾端多餘的連結。
        ListNode tmp = outputHead;
        while (list1 != null || list2 != null) {
            tmp.next = new ListNode(); // 在迴圈的開頭才創造新 ListNode，這樣才不會在尾端多造出一個。
            tmp = tmp.next;
            if (list1 != null && list2 != null) {
                if (list1.val <= list2.val) {
                    tmp.val = list1.val;
                    list1 = list1.next;
                } else {
                    tmp.val = list2.val;
                    list2 = list2.next;
                }
            } else if (list1 != null) {
                tmp.val = list1.val;
                list1 = list1.next;
            } else if (list2 != null) {
                tmp.val = list2.val;
                list2 = list2.next;
            }
        }
        return outputHead.next;
    }
}

依序比較 list1 與 list2 的大小來創建 outputHead。

檢討

其他人滿多使用遞迴方式解題，我有點難理解，暫時先無視。