vlambda博客
学习文章列表

19.Remove Duplicates from Sorted List（删除有序链表中重复元素）

前言：
前面我们在顺序表中做过同样的事情，这里也差不多，都是两个表的意思（双指针）。

文字思想：

这是一个“有序单链表”，假设表是递增的，则值重复的元素一定是相邻的。

①将表划分为A表，B表；A表是该有序单链表的前半部分，B表是该表的后半部分；

②初始时，表A中只有一个元素，也就是有序单链表的第一个元素；表B拥有剩下的n-1个元素；

③用表A的最后一个元素与表B从头开始比较，出现了不相等时，追加到表A尾巴上；相等的在C++中需要free，我们是用Java写的，有自动垃圾回收机制，所以不操心释放的问题。

④重复③，直到表B为空；

例子：

代码：

复杂度：

时间复杂度：O(n)；空间复杂度：O(1)。

积累：

1. 一个线性表分为几部分的逻辑模型。

2. 整体。