【LeetCode】 206. Reverse Linked List 解答・解説【Python】

はじめに
1. ポイント
2. この記事で得られること
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python, iterative(反復)
終わりに

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- 連結リスト

この記事で得られること

- 連結リストの扱い方の練習ができます。

詳細

問題

原文

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

1
2

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2] Output: [2,1]

1
2

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = [] Output: []

1
2

Input: head = []
Output: []

Constraints:

The number of nodes in the list is the range [0, 5000].

-5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

内容(和訳)

単方向連結リストheadが与えられます。

リストを反転させて返してください。

※正しくない可能性があります。

解答

解答1：Python, iterative(反復)

#連結リストheadの先頭から最後まで進めながら、反転された連結リストを作る。
#headの次のノードを一度退避させ、

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        previous_node = None
        current_node = head
        while current_node:
            #現ノードのnextに保持されているノードを一旦退避させる。
            #現ノードのnextには前のノード(反転後の次のノード)を入れるため
            next_node = current_node.next
            #現ノードのnextに前のノードを入れる。1周目はNone(連結リストの終端)が入る
            #反転時に次のノードになる。
            current_node.next = previous_node
            #現ノードは、次の周回では前のノードとなるので、previous_nodeに入れる。
            #次の周回では、次のノードのnextとして代入される
            previous_node = current_node
            #現ノードから次のノードへ移動する
            current_node = next_node
        return previous_node

#連結リストheadの先頭から最後まで進めながら、反転された連結リストを作る。

#headの次のノードを一度退避させ、

# Definition for singly-linked list.

# class ListNode:

# def __init__(self, val=0, next=None):

# self.val = val

# self.next = next

class Solution:

def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

previous_node = None

current_node = head

while current_node:

#現ノードのnextに保持されているノードを一旦退避させる。

#現ノードのnextには前のノード(反転後の次のノード)を入れるため

next_node = current_node.next

#現ノードのnextに前のノードを入れる。1周目はNone(連結リストの終端)が入る

#反転時に次のノードになる。

current_node.next = previous_node

#現ノードは、次の周回では前のノードとなるので、previous_nodeに入れる。

#次の周回では、次のノードのnextとして代入される

previous_node = current_node

#現ノードから次のノードへ移動する

current_node = next_node

return previous_node

・連結リストについて

LeetCodeでの単方向連結リストはノードと呼ばれる要素が連なってできています。

各ノードはListNodeと呼ばれるクラスで定義され、valという値を示す属性と、nextという次のノードを示す属性を持ちます。

valにはintの数字、nextには次のノード(ListNodeのインスタンス)が入ります。

現在のノードから次のノードを指し示すにはListNodeクラスのnext属性に代入することで可能です。

・この問題を解く方法について。

前から後ろに各ノードを一巡して走査しながら、以下の操作を行います。

現在のノードのnextを一旦別の変数に入れる

現在のノードのnextに、別の変数に入れておいた前のノードを入れる

現在のノードを前のノードとして別の変数に入れる

現在のノードにnextに入れておいたノードを入れることで、次のノードへ移動する

前のノードには、先頭の要素が最後尾に、最後尾の要素が先頭になった連結リスト(この問題の解答)が入っているのでこれを戻り値として終了します。

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

疑問が解決した方は他の問題もどうぞ

前：1572. Matrix Diagonal Sum

次：

LeetCode 解答・解説記事一覧

疑問が解決しない方はこちらへ

・連結リストを作るためのListNodeクラスがありますが、クラスに初めて触れる方はこちらへどうぞ。

Pythonのクラスの概要と使い方を整理

・連結リストについてまとめたページもあります。

連結リストの概要・イメージ・実装・使い方を整理