Neunomizuの日記

俺だけが俺だけじゃない

# LeetCode Easy 234. Palindrome Linked List

tags: leetcode

問題

イデア

「単方向連結リストが与えられた時,それが左右対称か判定しろ」という問題です.

実装するだけの問題ですね…これも(自力で出来なかった顔)

解法

  • 連結リストリストを前半と後半に分けます.
    • ポインタを1つずつ動くものと,2つずつ動くものに分け,これによって中心のノードを特定します.
    • 中心のノードから後半部分のノードを反転させます.
  • そして,反転させたノードとheadを比較して異なった値が出てくればFalseです
    • 出てこなければTrue

計算量

配列のノードの数を$N$とします.

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(1)$

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
            if not head:
                return True

            fast = slow = head
            while fast and fast.next:
                fast, slow = fast.next.next, slow.next

            rev = None
            while slow:
                next_node = slow.next
                slow.next = rev
                rev = slow
                slow = next_node

            while rev:
                if rev.val != head.val:
                    return False
                rev = rev.next
                head = head.next
            return True

# LeetCode Medium 19. Remove Nth Node From End of List

tags: leetcode

問題

イデア

「後ろからn番目のノードを連結リストから取り除け」という問題です.

2つのポインタを使います.

解法

  • 片方のポインタをnつ先に進め,このポインタが末尾にたどり着いたときのもう片方のポインタが答えです.

計算量

リストの大きさを$N$とする.

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(1)$

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        fast = slow = dummy
        for _ in range(n):
            fast = fast.next
        while fast and fast.next:
            fast = fast.next
            slow = slow.next
        slow.next = slow.next.next
        return dummy.next

# LeetCode Medium 328. Odd Even Linked List

tags: leetcode

問題

イデア

「与えられた単方向連結リストの奇数番目のノード群から繋げて,偶数番目のノード群を繋げろ」という問題です.つまり1->2->3->4->5->NULL1->3->5->2->4にしろということです(1-indexed).

更にin-place,つまり空間計算量$O(1)$で実装する必要があります.また,ノードの元々の順番を考慮して奇数番目,偶数番目のノードを繋げる必要が有ります.

解法

  • 奇数と偶数のノードを指す変数を用意します.
  • これらを付け替えます.

計算量

単方向連結リストのノードを$N$をとします.

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(1)$

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def oddEvenList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        odd = head
        even = head.next
        even_head = even
        while even and even.next:
            odd.next = odd = even.next
            even.next = even = odd.next
        odd.next = even_head
        return head

# LeetCode Easy 203. Remove Linked List Elements

tags: leetcode

問題

イデア

valという値を連結リストから取り除け」という問題です.

やるだけです.

解法

  • 先頭からvalと同じ値を持つノードを取り除きます.
  • 問題の連結リストは単方向連結リストなので,node1->node2->node3->...と繋がっている際に,node1を削除するにはその前のノードが必要です.
  • そのため,ダミーのヘッドを作り,その先頭を指す変数cur_nodeを作ります.
  • cur_nodeの次のノードの値がvalと同じならば,cur_nodeを次の次のノードに繋ぎます.
    • これによって,valと同じ値を持つノードを取り除くことが出来ます.

計算量

リストの大きさを$N$とする.

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(1)$

Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        dummy_head = ListNode(0)
        dummy_head.next = head
        cur_node = dummy_head
        
        while cur_node.next:
            if cur_node.next.val == val:
                cur_node.next = cur_node.next.next
            else: 
                cur_node = cur_node.next
        return dummy_head.next

# LeetCode Easy 26. Remove Duplicates from Sorted Array

tags: leetcode

問題

イデア

「ソートされた配列から同じ要素を取り除いたサイトの配列の大きさを返せ」という問題です.

ただし,in-placeなアルゴリズムにせよとのこと.つまり$O(1)$で解く必要があります.

整列されているという特徴を活かした問題を解いていきます.

解法

  • 最後に参照した要素をlast_numとして保存します.
  • 配列で現在見ている要素を指す添字をcur_posとし,この要素がlast_numと同じか,違うかで分岐させます.

計算量

配列の大きさを$N$とします.

  • 時間計算量
    • $O(N)$
  • 空間計算量
    • $O(1)$

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        cur_pos = 0
        last_num = None
        while cur_pos < len(nums):
            if nums[cur_pos] == last_num:
                nums.pop(cur_pos)
            else:
                last_num = nums[cur_pos]
                cur_pos += 1
                
        return cur_pos