算法题--删除单向链表中的重复元素II

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