# LeetCode Medium 24. Swap Nodes in Pairs

tags: leetcode

問題

• Explore
• 普通の

連結リストが与えられ, 全ての隣り合った2つのノードを交換し先頭のノードを返せ

リストのノードの値は変更してはいけなく,ノード自身を変えることだけができる

解法1

連結リスト

まずは連結リストが何かを理解する必要が有ります

連結リストは値とポインタを持つ構造体です

この問題で与えられる連結リストは以下のような単方向連結リストです

この先頭のポインタを受け取り,再帰的に連結リストのポインタを付け替えて最後にその先頭のノードを返せという問題です

再帰的な解法

• headという先頭のノードが与えられます
• この先頭ノードを1, 1が指すノードを2, 2が指すノードを3...とします

• まずは基底を考えます
  • 再帰的な関数が終了するのはNULLを指すポインタを返したときですね
  • headの先がNULLもしくはheadの次のノードがNULLを指す時に終了するようにします
• 次に再帰的にこの問題が解けるように定義します
  • 1と2で問題が解決し,3で再び同じ問題を解決すると定義すれば良いです
• 2をnew_hという名前の新しい先頭のノードにします
  • そして,1が3を指すようにします
  • そして,3で同じ処理が行われるようにします
• 下の図で書かれている赤い矢印がここで行うポインタの移し替えです

• 連結リストのノードの数を$n$として
  • 空間計算量は$O(n)$
  • 時間計算量は$O(n)$

Python

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

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
      if head == None or head.next == None:
        return head
      new_h = head.next
      head.next = self.swapPairs(new_h.next)
      new_h.next = head
      return new_h

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* new_h = head->next;
        head->next = swapPairs(new_h->next);
        new_h->next = head;
        return new_h;
    }
};

解法2

これはiterative(再帰とは異なりforなどの繰り返し処理で解くことを意味します)にも解けます

これは再帰関数を使わずスタック領域を使わないので空間計算量が$O(1)$に改善されます

上でやったことをiterativeにやるには次のようにします

• 空のListNodeを指すポインタnew_hを作ります
• このポインタがheadを指すようにします
  • そして,new_hをコピーしたptrを使います
  • このptrの次のノードがNULLでなく,ptrの次の次のノードもNULLでない間上のポインタの移し替えをします

Python

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

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
      new_h = ListNode(None)
      new_h.next = head
      ptr = new_h
      while ptr.next != None and ptr.next.next != None:
        node1, node2, node3 = ptr.next, ptr.next.next, ptr.next.next.next
        ptr.next = node2
        ptr.next.next = node1
        ptr.next.next.next = node3
        ptr = node1
      return new_h.next

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
      ListNode* new_h = new ListNode(NULL);
      new_h->next = head;
      ListNode* ptr = new_h;
      while(ptr->next && ptr->next->next) {
        ListNode* node1 = ptr->next;
        ListNode* node2 = ptr->next->next;
        ListNode* node3 = ptr->next->next->next;
        ptr->next = node2;
        ptr->next->next = node1;
        ptr->next->next->next = node3;
        ptr = node1;
      }
      return new_h->next;
    }
};