# LeetCode Easy 21. Merge Two Sorted Lists

tags: leetcode

問題

• Explore
• Problems

2つの整列済みのリストを合併し, 新しいリストとして返せ.

2つのリストの先頭のノードを切り出して新しいリストは作られます

解法1(iterative)

この解法ではdummyというポインタを作ります.このポインタが指す先をtailとします

このtailに他の2つのリストの先頭のノードのうち, 値が小さい方を繋げていきます

最終的にこのdummyの先に付いているポインタを返せば良いです

図

図示すると下のようになります

tailにノードを繋げて, tailを繋げたノードにすることで常にtailはdummyの指すノードから始まる連結リストの末尾になります

計算量

入力l1とl2の長さをそれぞれ$n$, $m$とします

• 空間計算量
  • 空間計算量は答えとして出力するために用意するdummmy連結リストの分が必要なので$O(1)$
• 時間計算量
  • 2つのリストからdummyにノードを付けるのが$O(1)$で, それを$n+m$回やるので$O(n+m)$です

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
  def mergeTwoLists(self, l1, l2):
      dummy = tail = ListNode(0)
      while l1 and l2:
          if l1.val < l2.val:
              tail.next = l1
              l1 = l1.next
          else:
              tail.next = l2
              l2 = l2.next
          tail = tail.next
      tail.next = l1 or l2
      return dummy.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
      ListNode* dummy = new ListNode(0);
      ListNode* tail = dummy;
      while(l1 && l2) {
        if (l1->val < l2->val) {
          tail->next = l1;
          l1 = l1->next;
        } else {
          tail->next = l2;
          l2 = l2->next;
        }
        tail = tail->next;
      }
      tail->next = l1 ? l1 : l2;
      return dummy->next;
    }
};

解法2(recursive)

再帰的に解くには片方が空のリストなときを基底とします

そして, 2つのリストの先頭のノードを比較して小さい方に再帰関数の結果を付け返します

つまり, l1もしくはl2のうち先頭の小さい方がiterativeでのtailの役割をしているわけです

計算量

• 空間計算量
  • ここではそれまでのリストしか使わないので$O(1)$
• 時間計算量
  • 解法1と同様に$O(n+m)$です

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
  def mergeTwoLists(self, l1, l2):
      if not l1 or not l2:
          return l1 or l2
      if l1.val < l2.val:
          l1.next = self.mergeTwoLists(l1.next, l2)
          return l1
      else:
          l2.next = self.mergeTwoLists(l1, l2.next)
          return l2

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
      if (l1 and l2) {
        if (l1->val < l2->val) {
          l1->next = mergeTwoLists(l1->next, l2);
          return l1;
        } else {
          l2->next = mergeTwoLists(l1, l2->next);
          return l2;
        }
      } else {
        return l1 ? l1 : l2;
      }
    }
};