LeetCodeに毎日挑戦してみた 83. Remove Duplicates from Sorted List(Python、Go)


はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門+アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

19問目(問題83)

83. Remove Duplicates from Sorted List

問題内容

Given a sorted linked list, delete all duplicates such that each element appear only once.

(日本語訳)

ソートされたリンクリストを指定して、各要素が1*回*だけ表示されるように、すべての重複を削除します。

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

考え方

  1. headの参照をcurにコピーします。

  2. curをwhileループで回していき、cur.valとcur.next.valを比較して次のvalともし同じだったら次のノードを上書きします。

  3. 違う場合はそのままノードを進めていきます。

  4. 戻り値にはheadを返します。

  • 解答コード
class Solution(object):
    def deleteDuplicates(self, head):
        cur = head
        while cur and cur.next:
            if cur.next.val == cur.val:
                cur.next = cur.next.next
            else:
                cur = cur.next
        return head
  • Goでも書いてみます!
func deleteDuplicates(head *ListNode) *ListNode {
    cur := head
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == cur.Val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return head
}