# LeetCode Easy 206. Reverse Linked List

tags: leetcode

問題

• Explore
• Problems

片方向リストを反転させよ

追加: recursiveとiterative両方で実装せよ

解法1(recursive)

• 以前の文字列の問題と同じです
• 反転された部分と反転されていない部分に分けます
• 反転された部分に反転されていない部分の先頭のポインタを移し替えます
• そして,反転されていない部分の先頭の次のノードを反転されていない部分の先頭のノードとしま
• 以下の図のようにポインタを付け替えます

• headが最後の要素ならばそのまま返します
• そうでないときはnew_hという新しく返す先頭のノードを作ります(NULLとします)
• そこに反転された連結リストを返します
  • ここに再帰関数を使います
• 次にheadの次のノードをheadに繋げ, headをNULLに繋げます
• 連結リストの長さを$n$とする
  • 空間計算量は再帰を$O(n)$回し, それぞれ$O(n)$の長さの配列を用意するので$O(n^{2})$
  • 時間計算量は再帰を$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 reverseList(self, head: ListNode) -> ListNode:
      if (head == None or head.next == None):
        return head
      new_h = self.reverseList(head.next)
      head.next.next = head
      head.next = None
      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* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
          return head;
        }
      ListNode* new_h = reverseList(head->next);
      head->next->next = head;
      head->next = NULL;
      return new_h;
    }
};

PPPP

解法2(iterative)

再帰と同じようにやります.以下の図のように実装します

• new_hという反転された配列とrestという反転されていない配列に分けます
  • new_hは最初NULLで, restはheadです
• これをrestが空になるまで以下の処理を行います
  • restの先頭のノードをnew_h に繋げます
  • restの先頭のノードを以前のrestの先頭のノードに繋がっていたノードに変えます
  • new_hの先頭のノードをさっきnew_hに繋げたrestのノードに変える
    • C++ではこのためにnext_hを使う
• 計算量は再帰の場合と同じです

Python

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

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
      new_h, rest = None, head
      while(rest):
        new_h, new_h.next, rest = rest, new_h, rest.next
      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* reverseList(ListNode* head) {
      ListNode* new_h = NULL;
      ListNode* rest = head;
      while(rest) {
        ListNode* next_h  = rest->next;
        rest->next = new_h;
        new_h = rest;
        rest = next_h;
      }
      return new_h;
    }
};