1.题目
82. 删除排序链表中的重复元素 II
难度中等746收藏分享切换为英文接收动态反馈
存在一个按升序排列的链表,给你这个链表的头节点 head ,请你删除链表中所有存在数字重复情况的节点,只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
示例 1:
输入:head = [1,2,3,3,4,4,5] 输出:[1,2,5]
示例 2:
输入:head = [1,1,1,2,3] 输出:[2,3]
2.题解
解题思路
遍历两次,第一次去重,把重复元素的值保存,第二次再次遍历。
代码
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var deleteDuplicates = function(head) {
const dum = new ListNode(-1000);
dum.next = head;
let cur = dum;
let arr = [];
while (cur && cur.next) {
let next = cur.next;
if (next.val !== cur.val) {
cur = cur.next;
} else {
arr.push(cur.val);
cur.next = cur.next.next;
}
}
let p = dum;
console.log('p', p);
while(p && p.next) {
let val = p.next.val;
if(arr.indexOf(val) > -1) {
p.next = p.next.next;
} else {
p = p.next;
}
}
return dum.next;
};
上面的方法比较笨,还有一种办法是。:
就是遍历的是 用两个变量cur.next, cur.next.next 内部嵌套while去重x
var deleteDuplicates = function(head) {
if (!head) {
return head;
}
const dummy = new ListNode(0, head);
let cur = dummy;
while (cur.next && cur.next.next) {
if (cur.next.val === cur.next.next.val) {
const x = cur.next.val;
while (cur.next && cur.next.val === x) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
};