Remove Duplicates from Sorted List
Given a sorted linked list, delete all duplicates such that each element appear only once. [#83]
Examples: Input: 1->1->2 Output: 1->2 Input: 1->1->2->3->3 Output: 1->2->3
题意：给定已排序的链表，删除所有重复项，使每个元素只显示一次
遍历出链表所有元素，转化成列表处理掉重复项，再遍历列表创建结果链表
>>> class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next def __repr__(self): return f'NodeList[{self.val}->{self.next}]' def __str__(self): return f'{self.val}->{self.next}' @property def values(self): ret,cur = [],self while cur: ret.append(cur.val) cur = cur.next return ret def build(lst: list): ret = Node(lst[0]) cur = ret for i in lst[1:]: cur.next = Node(i) cur = cur.next return ret def delDup(node): lst1,lst2 = [],node.values for i in lst2: if i not in lst1: lst1.append(i) return Node.build(lst1) >>> in1 = Node.build([1,1,2]) >>> in1 NodeList[1->1->2->None] >>> out1 = Node.delDup(in1) >>> out1 NodeList[1->2->None] >>> >>> in2 = Node.build([1,1,2,3,3]) >>> in2 NodeList[1->1->2->3->3->None] >>> out2 = Node.delDup(in2) >>> out2 NodeList[1->2->3->None] >>>
上面这是偷懒的做法，但遍历了2次，取值和创建节点各一次遍历。正规的做法只要遍历一次，在遍历的同时创建符合结果要求的节点链表，就相当于在有条件地复制一个已节点。用以下函数替换上面的 delDup() 其它不变，再做测试：
def removeDup(node): ret = Node() p1,p2 = node,ret # 相当于设置了2个“指针” while p1 is not None: if p1.val != p2.val: p2.next = Node(p1.val) p2 = p2.next p1 = p1.next # “指针”向后移动 return ret.next # 加上.next 去掉“空”的“头节点” >>> a = Node.build([1,1,2,3,3]) >>> Node.removeDup(a) NodeList[1->2->3->None] >>> b = Node.build([1,2,2,3,4,4,4,5]) >>> Node.removeDup(b) NodeList[1->2->3->4->5->None] >>>
Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. [#82]
Examples: Input: 1->2->3->3->4->4->5 Output: 1->2->5 Input: 1->1->1->2->3 Output: 2->3
题意：给定已排序的链表，删除所有重复项，只留不重复元素
和上题一样，先遍历出数据，完成任务后再创建节点，也是偷懒的做法：
>>> class Node(): def __init__(self, value=None, Next=None): self.val = self.value = value self.next = Next def __repr__(self): return f'NodeList[{self.val}->{self.next}]' def __str__(self): return f'{self.val}->{self.next}' @property def values(self): ret,cur = [],self while cur: ret.append(cur.val) cur = cur.next return ret def build(lst): ret = Node(lst[0]) cur = ret for i in lst[1:]: cur.next = Node(i) cur = cur.next return ret def delDup2(node): lst1 = node.values lst2 = [i for i in lst1 if lst1.count(i)==1] return Node.build(lst2) >>> in1 = Node.build([1,2,3,3,4,4,5]) >>> in1 NodeList[1->2->3->3->4->4->5->None] >>> out1 = Node.delDup2(in1) >>> out1 NodeList[1->2->5->None] >>> in2 = Node.build([1,1,1,2,3]) >>> in2 NodeList[1->1->1->2->3->None] >>> out2 = Node.delDup2(in2) >>> out2 NodeList[2->3->None] >>>
这题的正规做法： 头、尾节点除外，只遍历所有中间节点，它们的值与前后两个节点值比较，都不相等才能进入结果链表；头节点只和自己的后续节点比较，尾节点只和自己的前驱节点比较。
def removeDup(node): ret = Node() p1,p2 = node,ret if not Node.isNode(p1.next): return node if p1.val != p1.next.val: p2.next = Node(p1.val) p2 = p2.next t = p1.val p1 = p1.next while p1.next is not None: if t != p1.val != p1.next.val: p2.next = Node(p1.val) p2 = p2.next t = p1.val p1 = p1.next if t != p1.val: p2.next = Node(p1.val) return ret.next if ret.next!=None else Node() '''' # 测试结果： >>> a = Node.build([1,2,3,3,4,4,5]);removeDup(a) Node(1->2->5->None) >>> b = Node.build([1,1,1,2,3]);removeDup(b) Node(2->3->None) >>> >>> b = Node.build([1,1]);removeDup(b) Node(None->None) >>> b = Node.build([1,2]);removeDup(b) Node(1->2->None) >>> b = Node.build([1,2,2]);removeDup(b) Node(1->None) >>> b = Node.build([1,1,2]);removeDup(b) Node(2->None) >>> b = Node.build([0,0,1,2,2,2,3,3]);removeDup(b) Node(1->None) >>> b = Node.build([0,0,1,2,2,2,3]);removeDup(b) Node(1->3->None) >>> ''''
