// 辅助类:节点
class Node {
constructor(element){
this.element = element; // 当前节点的值
this.next = null // 当前节点指向下一个节点的指针
}
}
class likedList {
constructor(){
// 链表头
this.head = null;
// 链表长度
this.length = 0;
}
// 链表尾添加元素
append (element) {
var node = new Node(element);
if (this.head == null) {
// 只会在向链表添加第一次的时候执行
this.head = node
this.length++
} else {
var current = this.head;
while (current.next) {
current = current.next
}
//while执行完毕后,current.next 为null,current是链表的最后一项
current.next = node;
this.length++;
}
}
//链表某一个位置添加元素
insert (position, element) {
//越界
if (position > -1 && position < this.length) {
var node = new Node(element);
if (position == 0) {
var current = this.head;
this.head = node;
this.head.next = current
this.length++
} else {
var index = 0;
var current = this.head;
var previous = null;
while (index < position) {
previous = current;
current = current.next;
index++;
}
previous.next = node;
node.next = current
}
this.length++
}
}
// 删除某一个位置的元素
removeAt (position) {
if (position > -1 && position < this.length) {
if (position == 0) {
this.head = this.head.next;
} else {
var current = this.head;
var previous = null;
var index = 0;
while (index < position) {
previous = current;
current = current.next;
index++;
}
// 出循环的时候,index == position
previous.next = current.next
}
this.length--;
return current //返回删除项
}
return null
}
//删除某一项
remove (element) {
return this.removeAt(this.indexOf(element))
}
// 查找
indexOf (element) {
var current = this.head;
var index = 0;
while (current) {
if (current.element == element) {
return index
}
index++;
current = current.next
}
return -1
}
isEmpty () {
return this.length == 0
}
size () {
return this.length
}
getHead() {
return this.head
}
}
链表的反转
const reverseList = function(head) {
// 初始化前驱结点为 null
let pre = null;
// 初始化目标结点为头结点
let cur = head;
// 只要目标结点不为 null,遍历就得继续
while (cur !== null) {
// 记录一下 next 结点
let next = cur.next;
// 反转指针
cur.next = pre;
// pre 往前走一步
pre = cur;
// cur往前走一步
cur = next;
}
// 反转结束后,pre 就会变成新链表的头结点
return pre
};
链表
像火车,车厢和车厢之间连接,可以随时替换车厢。链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大
链表的模拟实现
链表的反转
链表的删除
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
真题描述:给定一个排序链表,删除所有含有重复数字的结点,只保留原始链表中 没有重复出现的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
集合
es6中的set,不再赘述
字典
js中的对象,不再赘述