题目分析:
移除的方法是把要移除节点的前节点的后继 指向 要移除节点的后继。
那就需要两个指针来保存两个节点的位置。
判断重复值,需要当前节点跟当前节点的后继来比较。
构造各种用例完善程序结构。
比如:
头两个节点相同。
最后两个节点相同。
中间两件两个节点相同。
分析这些用例,结合题目的要求,获知
1.运动到 快指针和快指针的后继值不同
2.运动到 快指针和快指针的后继值相同 直到获取不同的后继值
3.获取到不同的后继值 之后的运算
这三者运算逻辑都不一样。
var linkList = {
val: 1,
next: {
val: 1,
next: {
val: 0,
next: {
val: 2,
next: {
val: 2,
next: {
val: 5,
next: {
val: 6,
next: {
val: 6
}
}
}
}
}
}
},
};
/*
运动的生成原则:
以空间的可复用性和运动的可复用性出发,
如果一个空间的复用满足不了,再申请一个空间。
如果一个运动的复用满足不了,再申请一个运动。
为什么要这样的运功方式,这样的用例?
自己的解题经验和直觉。以及链表的本质。
边界条件:链表头部节点为空或者只有一个节点。
初始空间:慢指针,快指针,快指针的后继。
初始状态:慢指针为undefined,快指针指向第一个节点,
主运动循环逻辑:
0. 快指针未走完链表。
1. 快指针跟快指针的后继值不同,慢指针走向快指针,快指针往前走一步。
2. 快指针跟快指针的n后继值相同,快指的后继针往前走一步。
3. 头部判断;是头部头节点指向快指针的后继;非头部慢指针指向快指针的后继。
4. 快指针往前走一步。
*/
var deleteDuplicates = function (head) {
if (head === undefined || head.next === undefined) {
return head;
}
var slow = head;
var fast = head;
// 遍历所有节点
while (fast) {
// 快指针的后继
var _next = fast.next;
// 链表末尾判断
if (_next === undefined) {
return head;
}
// --- 快指针跟快指针的后继值不同,则慢指针走向快指针,快指针往前走一步 ---
if (fast.val !== _next.val) {
slow = fast;
fast = _next;
continue;
}
// ---
// --- 快指针跟快指针的后继值相同,快指针的后继往前走一步 ---
while (_next !== undefined && _next.val == fast.val) {
_next = _next.next;
}
// 快指针跟快指针的后继值不同
// 链表头部重复,更新链表头部
if (fast === head) {
head = _next;
}
else {
// 非链表头部重复,即链表中间或链表结尾
slow.next = _next
}
// 继续遍历
fast = _next;
// ---
}
return head;
}
var result = deleteDuplicates(linkList);
console.log(result);
尴尬的更新20180726
const linkList = {
val: 1,
next: {
val: 1,
next: {
val: 0,
next: {
val: 2,
next: {
val: 2,
next: {
val: 5,
next: {
val: 6,
next: {
val: 6
}
}
}
}
}
}
},
};
const DeleteSameElem = function(List){
let pre = List;
let next = List.next;
while(next !== undefined ){
if(pre.val === next.val){
pre.next = next.next;
next = next.next;
}
else{
next = next.next;
pre = pre.next;
}
}
return List
}
const result = DeleteSameElem(linkList);
console.log(result);