【LeetCode】206. Reverse Linked Listを解く

問題へのリンク

問題概要

連結リストheadが与えられる．headを逆順にしたものを返せ．

例：

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

制約

• ノードの数 $0 \leq N \leq 5000$
• $-5000 \leq Node.val \leq 5000$

考えたこと

まず，head = []のときはnullを返せば良い．

次に，例えばhead = [1,2]のときは先頭から順にノードを見ていき，

ステップ	res	head
1	null	1 -> 2 -> null
2	null <- 1	2 -> null
3	null <- 1 <- 2	null

のように順番にhead.nextの向きをresの方へ変えていけば良い．

この手法は，長さ$N$のノードについて適用しても所望の解を得られる：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        res = None
        while head:
            curr = head # 向きを反転させるターゲットのノード
            head = head.next
            curr.next = res # ターゲットのノードの向きをresへ向ける
            res = curr
        return res

注意点

上記コードのwhile部分について，以下のように順番を変えてみるとどうなるだろうか？

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        res = None
        while head:
            curr = head
            curr.next = res
            res = curr
            head = head.next # changed
        return res

一見，resに関連する処理と，headの移動の処理がまとまっているため分かりやすいコードに見える．

しかし，このコードの実行結果は

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

となり，所望の出力[2,1]が得られない．

なぜか？

while内のcurrとheadのidを出力してみると以下のようになる．

while head:
  curr = head # id(head) = 139995350720656
              # id(curr) = 139995350720656
  curr.next = res
  res = curr
  head = head.next # changed

ご覧の通り，currとheadは同じポインタを指していることが分かる．

従って，curr.next = resとhead.next = resは等価な処理となり，この時点で

head : null <- 1

のように上書きされてしまうのである．

一方，元のコードの場合を見てみると

while head:
    curr = head
    head = head.next
    curr.next = res # ターゲットのノードの向きをresへ向ける
    res = curr

curr = headの時点ではid(head) == id(curr)であるが，その次のhead = head.nextによってid(head) != id(curr)となる．

従って，curr.next = resによる上書きが発生しない．