LeetCode 面試題 02.01. 移除重複節點

題目

編寫代碼，移除未排序連結清單中的重複節點。保留最開始出現的節點。

示例1:

 輸入：[1, 2, 3, 3, 2, 1]
 輸出：[1, 2, 3]
示例2:

 輸入：[1, 1, 1, 1, 2]
 輸出：[1, 2]           

提示：

連結清單長度在[0, 20000]範圍内。

連結清單元素在[0, 20000]範圍内。

進階：

如果不得使用臨時緩沖區，該怎麼解決？

解題思路

class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        # #設定字典緩沖區
        # numDic = {}
        # headTemp = head
        # pre = head
        # while headTemp != None:
        #     # print(headTemp.val)
        #     dicKey = str(headTemp.val)
        #     if dicKey not in numDic:#如果沒值
        #         numDic[dicKey] = 1
        #         pre = headTemp
        #         headTemp = headTemp.next
        #     else:#如果有值
        #         # print(numDic)
        #         if pre.next.next is not None:#删除元素
        #             pre.next = pre.next.next
        #             headTemp = pre.next
        #         else:
        #             pre.next = None
        #             headTemp = None
        # return head
        #不設定緩沖區 python會逾時
        left = head
        while left != None:
            right = left.next
            rightPre = left
            while right != None:
                if right.val == left.val:#如果等值就删除
                    if rightPre.next.next is not None:
                        rightPre.next = rightPre.next.next
                        right = rightPre.next
                    else:#盡頭
                        rightPre.next = None
                        right = None
                        break
                else:#r指針向前周遊
                    right = right.next
                    rightPre = rightPre.next
            left = left.next#左指針周遊
        return head