【LeetCode】アルゴリズム体操 21. Merge Two Sorted Lists

LeetCode - Merge Two Sorted Lists

問題文

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.

だいたいの日本語訳

引数：ListNode list1, ListNode list2
戻り値：ListNode型のリンクしてるリストのいっちゃん最初

list1、list2っていうリンクしてるリストのいっちゃん最初をそれぞれあげるね。ちなみにソートされてるよ。
この2つのリストをいい感じのソート順でマージして、1個のリンクしてるリストを作ってな。そのいっちゃん最初を返してくれや。

なんだか長くなってしまった

Solution.java

/**
 * 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;
        
        ListNode lastList = null;
        
        // 初期化
        if (list1.val <= list2.val) {
            lastList = new ListNode(list1.val);
            list1 = list1.next;
        } else {
            lastList = new ListNode(list2.val);
            list2 = list2.next;
        }

        // 返却用のリスト
        ListNode ansList = lastList;
        
        // 両方のリストが存在する場合のみ比較
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                lastList.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                lastList.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            lastList = lastList.next;
        }
        
        // 片方のリストが残っていたらくっつける
        if (list1 != null) {
            lastList.next = list1;
        } else if (list2 != null) {
            lastList.next = list2;
        }
        
        return ansList;
    }
}

nextを返せばいい感じにまとまるかも

Solution.java

/**
 * 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;
        
        // 初期化
        ListNode lastList = new ListNode();
        // 返却用のリスト
        ListNode ansList = lastList;
        
        // 両方のリストが存在する場合のみ比較
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                lastList.next = new ListNode(list1.val);
                list1 = list1.next;
            } else {
                lastList.next = new ListNode(list2.val);
                list2 = list2.next;
            }
            lastList = lastList.next;
        }

        // 片方のリストが残っていたらくっつける
        if (list1 != null) {
            lastList.next = list1;
        } else if (list2 != null) {
            lastList.next = list2;
        }
        
        return ansList.next;
    }
}

実行結果

RunTimeはわりとタイミングによって変わりがち。

Title	RunTime	Memory
なんだか長くなってしまった	1ms	40MB
nextを返せばいい感じにまとまるかも	0ms	38.3MB

ひとこと

う゛～～～ん、なんかもっと賢いやり方がありますかね。