概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day77「1502. Can Make Arithmetic Progression From Sequence」

今はTop 100 Liked QuestionsのMediumを優先的に解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

Twitterやってます。

技術ブログ始めました！！
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします！

問題

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.

こちらですとゴチャゴチャせずに割とスッキリ書けるので僕はこちらの方が好きです。
それに少しですが、速度も改善されています。

二つの回答例を書いてみましたが、いかがでしょうか？

もっとこっちの方がスマートだし良くない？という意見をお持ちの方は是非コメントくださると嬉しいです。

ゼロから始めるLeetCode Day78 「206. Reverse Linked List」

概要

問題

解法