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

image.png

0. 链接

题目链接

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. 思路1：遍历处理每个重复模块

• 直观的思考, 本题的主要任务是: 找到重复模块并保留其中一个, 具体做法如下:
• 新建链表来存储结果
• 遍历过程中, 对于每一个cur, 需要通过cur.val == cur.next.val条件找到一个重复模块的最后一个元素, 将这个元素追加到新链表中
• 遍历完之后, 还需要将新链表的末尾节点的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:
        cur_new = new_head = ListNode(-1)
        cur = head
        while cur is not None:
            while cur.next is not None and cur.val == cur.next.val:
                cur = cur.next
            cur_new.next = cur
            cur_new = cur_new.next
            cur = cur.next

        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->3->4->5
==================================================

input:
1
output:
1
==================================================

input:
1->1
output:
1
==================================================

input:
1->1->1
output:
1
==================================================

input:
1->1->1->1->1->3->3->4->5
output:
1->3->4->5
==================================================

input:
1->2->2
output:
1->2
==================================================

4. 结果

image.png