刻意练习：LeetCode实战 -- Task08.删除排序链表中的重复元素

背景

本篇图文是LSGO软件技术团队组织的 第二期基础算法（Leetcode）刻意练习训练营 的打卡任务。本期训练营采用分类别练习的模式，即选择了五个知识点（数组、链表、字符串、树、贪心算法），每个知识点选择了 三个简单、两个中等、一个困难 等级的题目，共计三十道题，利用三十天的时间完成这组刻意练习。

本次任务的知识点：链表

链表（Linked List） 是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里除了存放本身数据（data fields）之外还存放其后继节点的指针（Pointer）。

使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

---

题目

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

示例 1:

输入: 1->1->2
输出: 1->2


示例 2:

输入: 1->1->2->3->3
输出: 1->2->3


---

实现

C# 语言

• 执行结果：通过

• 执行用时：160 ms, 在所有 C# 提交中击败了 5.23% 的用户

• 内存消耗：25.9 MB, 在所有 C# 提交中击败了 5.72% 的用户

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */

public class Solution
{
    public ListNode DeleteDuplicates(ListNode head)
    {
        if (head == null)
            return head;

        ListNode first = head.next;
        ListNode second = head;
        while (first != null)
        {
            if (first.val == second.val)
                second.next = first.next;
            else
                second = second.next;
            first = first.next;
        }
        return head;
    }
}


Python 语言

• 执行结果：通过

• 执行用时：52 ms, 在所有 Python3 提交中击败了 33.88% 的用户

• 内存消耗：13.5 MB, 在所有 Python3 提交中击败了 12.75% 的用户

# 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:
            return head

        first = head.next
        second = head
        while first is not None:
            if first.val == second.val:
                second.next = first.next
            else:
                second = second.next
            first = first.next
        return head


---

来源

• https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/

---