Zenn
🖋

LeetCode 206. Reverse Linked List (Python3)

に公開
Python
LeetCode
tech

はじめに

LeetCode 「206. Reverse Linked List」の問題を Python3 で解きました。

問題

https://leetcode.com/problems/reverse-linked-list/description/

問題文

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

和訳
単方向リストのヘッドが与えられるので、リストを反転し、反転したリストを返します。

例

1 → 2 → 3 → 4 → 5
        ↓
5 → 4 → 3 → 2 → 1

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

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

Input: head = []
Output: []

制約

  • The number of nodes in the list is the range [0, 5000].
  • -5000 <= Node.val <= 5000

解答1

単方向リストを反転させる問題です。
リストのノードを先頭から1つずつスタックに追加していき、その後スタックから1つずつpopしながら連結していくことで反転させることができます。

コード

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return head

        stack = []
        while head:
            stack.append(head)
            head = head.next

        new_head = stack.pop()
        curr = new_head
        while stack:
            curr.next = stack.pop()
            curr = curr.next
        
        curr.next = None
        return new_head

1つ目のwhileでスタックに順にノードを追加しています。
2つ目のwhileでスタックの最後の要素をnew_headとして、popしながらリストを反転させています。
なお、スタックの最後に残った要素はnextが元の状態のままなので、ループを抜けた後にcurr.next = Noneを設定することが必要です。

計算量

  • 時間的計算量：O(n)
    • 各ノード2回ずつ処理する
  • 空間的計算量：O(n)
    • 全てのノードをスタックにコピーするのでn個メモリが必要

解答2

スタックを使わずに解くこともできます。
この方法がメモリ効率が良いです。
リストをたどりながらポインタを張り替えてリストを逆順にする方法です。

コード

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            nxt = curr.next # 次のノードを保持
            curr.next = prev # 矢印の向きを逆にする
            prev = curr # prev を進める
            curr = nxt # curr を進める
        return prev

流れ

例：リストが以下の場合

1 -> 2 -> 3 -> None

初期状態

prev = None
curr = 1 -> 2 -> 3 -> None

1回目ループ

  1. nxt = curr.next
nxt = 2 -> 3 -> None
  1. curr.next = prev （1の next を逆向きにする）
1 -> None
  1. prev = curr
prev = 1 -> None
  1. curr = nxt
curr = 2 -> 3 -> None

2回目ループ

  1. nxt = curr.next
nxt = 3 -> None
  1. curr.next = prev
2 -> 1 -> None
  1. prev = curr
prev = 2 -> 1 -> None
  1. curr = nxt
curr = 3 -> None

3回目ループ

  1. nxt = curr.next
nxt = None
  1. curr.next = prev
3 -> 2 -> 1 -> None
  1. prev = curr
prev = 3 -> 2 -> 1 -> None
  1. curr = nxt
curr = None

ここでループが終了し、prevが新しいリストの先頭を指しています。

計算量

  • 時間的計算量：O(n)
    • 各ノード1回ずつ処理する
  • 空間的計算量：O(1)
    • 使うのはprev,curr,nxtの変数だけ
GitHubで編集を提案

Discussion