83. Remove Duplicates from Sorted List

1. 原始题目

Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2
Output: 1->2

Example 2:

Input: 1->1->2->3->3
Output: 1->2->3

2. 题目理解

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

没看清排序，所以最初写了一个稍稍复杂的代码。

3. 解题

思路:应为是排序，所以重复数字只看可能是相邻的。例如11112233369。重复的1互相挨着，重复的2也互相挨着。所以用两个指针分别滑动，前面的指针负责滑过所有重复元素，后面的指针负责将两个不同的元素相连。

1）适用于一切链表（可以是非排序的）。需借助一个列表来判断是否有重复元素

 1 class Solution:
 2     def deleteDuplicates(self, head: ListNode) -> ListNode:
 3         if not head:
 4             return None
 5         head_ = head
 6         i = head
 7         j = head.next
 8         unique = []         # 元素池。里面存放非重复元素
 9         while(j):
10             unique.append(i.val)      # 将新不重复元素添加
11             while j and (j.val in unique):
12                 j = j.next           # 过滤掉重复元素
13             i.next = j
14             i = i.next
15             if j:
16                 j = j.next
17         return head_ 

验证：

 1 listnode1 = ListNode_handle(None)
 2 s1 = [1,2,3,666,8,3,2,9,4,5,6,8,999,666]
 3 #s1 = [1,1]
 4 for i in s1:
 5     listnode1.add(i)
 6 listnode1.print_node(listnode1.head)
 7 
 8 
 9 s = Solution()
10 head = s.deleteDuplicates(listnode1.head)
11 listnode1.print_node(head)

1 2 3 666 8 3 2 9 4 5 6 8 999 666
1 2 3 666 8 9 4 5 6 999

2）对应于本题，不会有乱序。

 1 class Solution:
 2     def deleteDuplicates(self, head: ListNode) -> ListNode:
 3         if not head:
 4             return None
 5         head_ = head
 6         i = head
 7         j = head.next
 8         while(j):
 9             if i.val == j.val:
10                 j = j.next
11             else:
12                 i.next = j
13                 i = i.next
14                 j = j.next
15         i.next = j
16         return head_  

验证：

 1 listnode1 = ListNode_handle(None)
 2 #s1 = [1,2,3,666,8,3,2,9,4,5,6,8,999,666]
 3 s1 = [1,1,1,2,2,2,2,3,6,66,66,666,666,6666666]
 4 for i in s1:
 5     listnode1.add(i)
 6 listnode1.print_node(listnode1.head)
 7 
 8 
 9 s = Solution()
10 head = s.deleteDuplicates(listnode1.head)
11 listnode1.print_node(head)

1 1 1 2 2 2 2 3 6 66 66 666 666 6666666 1 2 3 6 66 666 6666666