問題: Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
1 brute force
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
found_values = []
current_node = head
while current_node:
if current_node.val not in found_values:
found_values.append(current_node.val)
current_node = current_node.next
dummy = ListNode()
last_node = dummy
for value in found_values:
last_node.next = ListNode(value)
last_node = last_node.next
return dummy.next
brute force
時間計算量: O(n) 空間計算量: O(n)
いっちゃんわかりやすいのでは！！？？
2 いらないノードを外していく。
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
current = head
while current:
while current.next and current.val == current.next.val:
current.next = current.next.next
current = current.next
return head
時間計算量: O(n) 空間計算量: O(1)
既存の連結リストをあれこれやって作る。
自分のノード視点から次のやつを見ていく気持ち。
「次のやつ……あー同じやつや、スキップ、また同じや、スキップ……違うやつきた! current = current.nextで飛び移れ！」
3
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
current = head
while current:
if current.next and current.val == current.next.val:
current.next = current.next.next
continue
current = current.next
return head
while conditions:
# do something
を
if conditions:
# do something
continue
に変換。自明すぎる。
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
current = head
while current and current.next:
if current.val == current.next.val:
current.next = current.next.next
continue
current = current.next
return head
こいつも自明な書き換え
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
else:
node_in_original = head
head_in_removed = ListNode(head.val)
node_in_removed = head_in_removed
while node_in_original:
while node_in_original.next and node_in_original.val == node_in_original.next.val:
node_in_original.next = node_in_original.next.next
node_in_original = node_in_original.next
node_in_removed.next = node_in_original
node_in_removed = node_in_removed.next
return head_in_removed
一応書いたけどうまみがなさげ。空間計算量は定数倍かな、多分。それにせよわざわざこれはないわ。