為自己Coding

YO~~ 剛跨入AI人工智慧領域的小小工程師, 熱愛自學, 熱愛分享, 下班後的我想為自己Coding, 積極撰寫教學文, 想將自學的程式知識分享給大家, 不斷追求進步的自己, 希望有一天能回饋社會,幫助需要幫助的人, 如果您有什麼很酷的想法,也覺得我還行,歡迎您找我合作~~

LeetCode筆記 - Linked List 鏈結串列方法 - LeetCode第83題 - 解法

發布於

Github連結

圖片來源: https://www.pexels.com/zh-tw/photo/326055/



1. 題目



說明: 給予一個排好序的鏈結串列,刪除掉裡面重複的元素,並回傳一個排好序的鏈結串列


2. 解法


方法一


Step 1: 如果鏈結串列為空,直接回傳鏈結串列

Step 2: 定義好目前的節點和它的上一個節點

Step 3: 只要目前指向的節點不為空,就表示還沒有繞過整個鏈結串列

  • 如果現在這個節點與上一個節點相同,就讓上一個節點直接指向目前節點的下一個節點,也就是把目前的節點移除掉,然後目前的節點也會移動到下一個節點
  • 如果目前與上一個節點不相等,就都移動到下一個節點

Step 4: 前面都過關並操作過了的話,就回傳整個修改好的鏈結串列,因為表示這個鏈結串列沒有其他重複的元素了

# Definition for singly-linked list.
# class ListNode:
#  def __init__(self, val=0, next=None):
#    self.val = val
#    self.next = next
class Solution:
  def deleteDuplicates(self, head: ListNode) -> ListNode:
    
    ## 如果鏈結串列為空,直接回傳
    if head == None:
      return head
    
    ## 目前的節點
    now = head.next
    ## 上一個節點
    prev = head
    
    ## 當目前的節點不為空
    while now != None:
      ## 如果現在這個節點與上一個節點相同,就讓上一個節點直接指向目前節點的下一個節點,也就是把目前的節點移除掉
      if now.val == prev.val:
        prev.next = now.next
        ## 然後目前的節點也會移動到下一個節點
        now = now.next
      
      
      ## 如果目前與上一個節點不相等,就都移動到下一個節點
      else:
        now = now.next
        prev = prev.next
    
    
    ## 回傳整個鏈結串列
    return head


方法二


作法

  • 創建一個用來遍歷所有節點now,它的位置和head一樣
  • 當now還未走到最後NIL時
  • 檢查前指定節點now的下一個節點n是否已經碰到NIL
  • 找當前指定節點now的下一個節點ne,並比較其值是否一樣,比到當值不相等為止
  • 並將now的下一個節點ne位置指向這個不相等的節點
  • 最後將指定節點now走到下一個節點ne
  • 反覆做循環直到now已經走過了整個Linked List,就回傳原本的head
class Solution:
  def deleteDuplicates(self, head: ListNode) -> ListNode:
    ## 創建當前的節點,從第一個開始
    now = head
    ## 當now還未走到最後NIL時
    while now != None:
      
      ## 下一個節點
      ne = now.next
      ## 當ne還沒碰到NIL的時候,而且其值與now的值相等
      while (ne != None) and (ne.val == now.val):
        ## 持續往下走
        ne = ne.next
        
      ## 當now和ne不相等的時候
      ## 把now的下一個節點位置指向它
      now.next = ne            
      ## now走到下一個節點
      now = ne
      
    return head

喜歡我的文章嗎?
別忘了給點支持與讚賞,讓我知道創作的路上有你陪伴。

CC BY-NC-ND 2.0 版權聲明

LeetCode筆記 - Linked List - 鏈結串列 - 觀念介紹

6

看不過癮?

一鍵登入,即可加入全球最優質中文創作社區