image.png
0. 链接
1. 题目
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Return the linked list sorted as well.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
2. 思路1：遍历处理每个重复模块
- 直观的思考, 本题的主要任务是: 找到重复模块并无视掉, 具体做法如下:
- 新建链表来存储结果
- 遍历过程中, 对于每一个
cur, 需要通过cur.val == cur.next.val条件找到一个重复模块的最后一个元素, 但这个元素是不能包含到新链表中的, 因此如果检测出重复元素存在, 则还需要向右移动一个位置; 否则将cur添加到新链表中 - 遍历完之后, 还需要将新链表的末尾节点的
next置为None
3. 代码
# coding:utf8
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
cur_new = new_head = ListNode(-1)
cur = head
while cur is not None:
has_dup = False
while cur is not None and cur.next is not None and cur.val == cur.next.val:
cur = cur.next
has_dup = True
if not has_dup:
cur_new.next = cur
cur_new = cur_new.next
cur = cur.next
if cur_new.next is not None:
cur_new.next = None
return new_head.next
def linked_list_to_array(head):
node = head
array = list()
while node is not None:
array.append(node.val)
node = node.next
return array
def array_to_linked_list(array):
head = ListNode(array[0])
node = head
for i in range(1, len(array)):
node.next = ListNode(array[i])
node = node.next
return head
def print_linked_list(head):
array = linked_list_to_array(head)
print('->'.join([str(x) for x in array]))
def my_test(solution, array):
head = array_to_linked_list(array)
print('input:')
print_linked_list(head)
print('output:')
print_linked_list(solution.deleteDuplicates(head))
print('=' * 50)
print('')
solution = Solution()
my_test(solution, [1, 2, 3, 3, 4, 4, 5])
my_test(solution, [1])
my_test(solution, [1, 1])
my_test(solution, [1, 1, 1])
my_test(solution, [1, 1, 1, 1, 1, 3, 3, 4, 5])
my_test(solution, [1, 2, 2])
输出结果
input:
1->2->3->3->4->4->5
output:
1->2->5
==================================================
input:
1
output:
1
==================================================
input:
1->1
output:
==================================================
input:
1->1->1
output:
==================================================
input:
1->1->1->1->1->3->3->4->5
output:
4->5
==================================================
input:
1->2->2
output:
1
==================================================
4. 结果
image.png
网友评论