ゼロから始めるLeetCode Day78 「206. Reverse Linked List」
概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始めるLeetCode Day77「1502. Can Make Arithmetic Progression From Sequence」
次回
ゼロから始めるLeetCode Day79「1282. Group the People Given the Group Size They Belong To」
(https://twitter.com/kueharx)やってます。
問題
206. Reverse Linked List
難易度はEasy。
問題としては、与えられた単方向の連結リストをそのままひっくり返すというものです。
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
解法
とりあえずiterativeなものを。
# 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: ListNode) -> ListNode:
pre,cur = None,head
while cur != None:
nex = cur.next
cur.next = pre
pre = cur
cur = nex
return pre
# Runtime: 44 ms, faster than 26.15% of Python3 online submissions for Reverse Linked List.
# Memory Usage: 15.3 MB, less than 67.33% of Python3 online submissions for Reverse Linked List.
pre,cur,nexという三つの変数を用意して一つ前、現在、一つ後の要素を保持してそれぞれ入れ替えていきます。
変数を用意してそれぞれの一時的な逃げ場所を作って上げるようなイメージで考えてみれば良いと思います。
ただ、これだとこの規模ならともかく、もっと変数が増えるようなケースだとなかなか処理の量が増えて書くのが面倒臭くなります。
やっぱり楽したいですよね。
では今度はstackを使ってみた解答です。
# 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: ListNode) -> ListNode:
if not head:
return None
stack = []
while head.next:
stack.append(head)
head = head.next
while stack:
cur = stack.pop()
cur.next.next = cur
cur.next = None
return head
# Runtime: 40 ms, faster than 46.28% of Python3 online submissions for Reverse Linked List.
# Memory Usage: 15.1 MB, less than 96.42% of Python3 online submissions for Reverse Linked List.
こちらですとゴチャゴチャせずに割とスッキリ書けるので僕はこちらの方が好きです。
それに少しですが、速度も改善されています。
二つの回答例を書いてみましたが、いかがでしょうか？
もっとこっちの方がスマートだし良くない？という意見をお持ちの方は是非コメントくださると嬉しいです。
コメント
コメントを投稿