原题地址：删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
解答
遍历，找到重复的元素删除即可。具体的实现代码如下：
/**
* @param {ListNode} head
* @return {ListNode}
*/
const deleteDuplicates1 = function(head) {
// 额外的头节点
let preHead = new ListNode(null);
preHead.next = head;
while (head && head.next) {
// 删除所有与当前节点重复的节点
while (head.next && head.val === head.next.val) {
head.next = head.next.next;
}
// 继续向后遍历
head = head.next;
}
return preHead.next;
};
测试：
let start = new Date();
const test = deleteDuplicates1;
console.log(listToString(test(arrayToList([1,1,2])))); // 1 -> 2
console.log(listToString(test(arrayToList([1,1,2,3,3])))); // 1 -> 2 -> 3
console.log(new Date().getTime() - start.getTime()); // 7
时间复杂度： 一次遍历，时间复杂度为$O(N)$
空间复杂度： 原地处理，空间复杂度为$O(1)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 28,2019