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

# <a href="https://leetcode.com/problems/merge-two-sorted-lists/">LeetCode - Merge Two Sorted Lists</a>

#### 問題文
>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個のリンクしてるリストを作ってな。そのいっちゃん最初を返してくれや。

## なんだか長くなってしまった
```java: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を返せばいい感じにまとまるかも
```java: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   |

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