Leetcode 206. Reverse Linked List

Problem

Linkedlistを反転させるという問題です。

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

InputとOutputの例は次になります。

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

Key Idea

Pointerを使ったIterativeな方法とRecursiveな方法があります。

Approach #1 : Iterative (Two Pointers)

Linked List の反転は、次のノードへの参照(next_temp)を保存してから、現在のノード(curr)の次のノードへの参照を更新し、前のノード(prev)を現在のノードに、現在のノードを次に保存したノードに更新するという一連のステップを繰り返すことで行います。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
            
        return prev

head = [1,2,3]とした場合の、挙動のイメージはこちらになります。

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。LinkedListを一回走査します。

• Space complexity: O(n)。ポインタしか使っていません。

Approach #2 : Recursive

Follow Up Questionとして、再帰で解くよう指定されています。
head.next（headの次の要素から始まる部分リスト）を再帰的に反転させます。
ここで、newHeadというポインタを用意し、常に反転リストの最初の要素を指しています。

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return None

        newHead = head
        if head.next:
            # head を反転させた部分リストの末尾に追加
            newHead = self.reverseList(head.next)
            head.next.next = head
        
        head.next = None

        # newHead は常に反転させた部分リストの先頭（元々のリストの末尾）を指す
        return newHead

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。LinkedListを一回走査します。

• Space complexity: O(n)。再帰的な解法では、リンクリストのノード数に応じたスタックフレームが生成されます。これは、再帰が深いレベルに達すると、そのレベルに応じてスタックフレームが確保され、それぞれの再帰ステップで状態が保存されるからです。

Reference