Github連結

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