203. Remove Linked List Elements

發表於 分類於 ， 閱讀次數： Disqus： 文章字數： 255

種類 : linked list
難度 : easy
題目 : 203. Remove Linked List Elements

思維邏輯

  1. 歷遍list
    1. 若cur_node.data == target:
      1. 若cur_node為head:
        更新head
      2. 若cur_node為尾(next==None):
        更新last.next, 並更新cur_node為last_node
      3. 否則:
        更新last.next為cur_node.next
    2. 紀錄last_node
    3. 更新cur_node
  2. 返回head

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
    def __repr__(self):
        return f'Node({self.data})'

class Solution:
    def removeElements(self, target):
        '''remove all of target in list'''
        cur_node = self.head
        last_node = None
        while cur_node:
            if cur_node.data == target:
                if cur_node == self.head:
                    self.head = cur_node.next
                elif cur_node.next == None:
                    last_node.next = None
                else:
                    last_node.next = cur_node.next
                    cur_node = last_node
            last_node = cur_node
            cur_node = cur_node.next
        return self.head
    def __repr__(self):
        nodes = []
        cur_node = self.head
        while cur_node:
            nodes.append(repr(cur_node))    # repr(), 將object轉為string
            cur_node = cur_node.next
        return '->'.join(nodes)

時間複雜度: O(n)
空間複雜度: O(1)

難點

  1. 當target重複出現時，需更新cur_node == last_node

最佳解法

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
        ans = ListNode(0, head)
        dummy = ans

        while dummy:
            while dummy.next and dummy.next.val == val:
                dummy.next = dummy.next.next
            dummy = dummy.next
        
        return ans.next

時間複雜度: O(n)
新增一個node在head前，就無須紀錄last_node
結束必須返回此node.next作為新的head