概述
链表是物理存储单元上非连续的、非顺序的存储结构，由一系列节点组成。
节点
节点包含两部分，一部分是存储数据元素的数据域，一部分是存储指向下一个节点的指针域。定义一个节点可以用如下代码：
function Node (data) {
this.data = data;
this.next = null;
}
链表中的第一个节点是首节点，最后一个节点是尾节点。
有头链表和无头链表
无头链表是指第一个节点既有数据域，又有指针域，第一个节点即是首节点又是头节点。有头链表是指第一个节点只有指针域，没有数据域。
有头链表.png
有头链表浪费空间，但是对于首个元素的操作（插入、删除等）可以跟其他节点相同，边界好处理。无头链表节省空间，但是处理时要注意边界情况。这里使用的是无头链表。
定义链表类：
function LinkList() {
// 定义节点
function Node (data) {
this.data = data;
this.next = null;
}
let length = 0; // 长度
let head = null; // 头节点
let tail = null; // 尾节点
}
给链表添加一些方法：
- append：添加一个新元素
- insert：在指定位置插入一个元素
- remove: 删除指定位置的元素
- indexOf: 返回指定元素的索引
- get: 返回指定索引位置的元素
- isEmpty: 判断链表是否为空
- print: 打印整个链表
function LinkList () {
// 定义节点
function Node (data) {
this.data = data;
this.next = null;
}
let length = 0; // 长度
let head = null; // 头节点
let tail = null; // 尾节点
this.append = function (data) { // 添加一个新元素
const node = new Node(data); // 创建一个新节点
if (!head) { // 如果是空链表，头节点和尾节点都指向新节点
head = node;
tail = node;
} else {
tail.next = node; // 尾节点指向新创建的节点
tail = node; // tail指向最后一个节点
}
length++;
return true;
}
this.insert = function (index, data) { // 在指定位置插入一个元素
if (index < 0 || index > length) { // 范围错误
return false;
}
const node = new Node(data);
if (index === 0) { // 如果在头节点前面插入，新的节点就变成了头节点
node.next = head;
head = node;
} else {
let amount = 1;
let currentNode = head;
while (amount < index) {
currentNode = currentNode.next;
amount++;
}
node.next = currentNode.next;
currentNode.next = node;
}
length++;
return true;
}
this.remove = function (index) { // 删除指定位置的元素
if (index < 0 || index >= length) {
return false;
}
let delNode = null; // 记录要删除的节点
if (index === 0) { // 如果删除头节点，head指向下一个节点
delNode = head;
head = head.next;
if (!head) { // 如果此时head是null，说明之前只有一个节点，删除之后变为空链表
tail = null; // 尾节点置空
}
} else {
let amount = 0;
let preNode = null;
let currentNode = head;
while(amount < index) {
preNode = currentNode;
currentNode = currentNode.next;
amount++;
}
delNode = currentNode;
preNode.next = currentNode.next;
if (!currentNode.next) { // 如果删除的是尾节点，tail指向前一个节点
tail = preNode;
}
}
length--;
tail.next = null;
return tail.data;
}
this.indexOf = function (data) { // 返回指定元素的索引
let currentNode = head;
let index = -1;
while (currentNode) {
index++;
if(currentNode.data === data) { // 有的话返回第一个
return index;
}
currentNode = currentNode.next;
}
return -1; // 如果没有返回-1
}
this.get = function (index) { // 返回指定索引位置的元素
if (index < 0 || index >= length) {
return null;
}
let currentIndex = 0;
let currentNode = head;
while (currentIndex < index) {
currentIndex++;
currentNode = currentNode.next;
}
return currentNode.data;
}
this.isEmpty = function () { // 判断链表是否为空
return length === 0;
}
this.print = function () { // 打印整个链表
let currentNode = head;
while (currentNode) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
}
}
之前用数组实现了栈和队列，现在可以基于链表实现。
为了实现方便，再给链表添加几个方法：
this.head = function () { // 返回头节点的值
return this.get(0);
}
this.tail = function () { // 返回尾节点的值
return this.get(length - 1);
}
this.removeHead = function () { // 删除头节点
return this.remove(0)
}
this.removeTail = function () { // 删除尾节点
return this.remove(length - 1)
}
基于链表实现的栈：
function Stack() {
let linkList = new LinkList();
this.push = function (item) { // 入栈
linkList.append(item);
}
this.pop = function () { // 出栈
return linkList.removeTail();
}
this.top = function () { // 返回栈顶元素
return linkList.tail()
}
}
基于链表实现的队列：
function Queue() {
let linkList = new LinkList();
this.enqueue = function (item) { // 入队列
linkList.append(item);
}
this.dequeue = function () { // 出队列
return linkList.removeHead();
}
this.head = function () { // 返回队首元素
return linkList.head();
}
this.tail = function () { // 返回队尾元素
return linkList.tail();
}
}
练习题
一、翻转链表
翻转之前：
link3.png
翻转之后：
link4.png
1、迭代翻转
假设有三个节点的一个链表，我们设preNode指向前一个节点, currentNode指向是当前要翻转的节点，在当前节点进行翻转：
currentNode.next = preNode;
在遍历过程中，每完成一个节点的翻转，都让currentNode = nextNode，指向下一个要翻转的节点，preNode和nextNode也一起向后滑动。
对于头节点来说，它翻转过后就是尾节点，尾节点的next指向null，所以初始化preNode = null;
link5.png
function reverseIter(head) {
if (!head) { // 如果是空链表，直接返回
return null;
}
let preNode = null; // 前一个节点
let currentNode = head; // 当前要翻转的节点
while(currentNode) {
let nextNode = currentNode.next; // 记录下一个节点
currentNode.next = preNode; // 翻转当前节点，让他指向前一个节点
preNode = currentNode; // 后移
currentNode = nextNode;
}
return preNode; // 返回翻转之后的头节点
}
- 递归翻转
看视频时听张老师说递归的精髓在于甩锅，你做不到的事情，让别人去做，等别人做完了，你在别人的基础上继续做。我觉得总结的很精辟。
- 首先明确函数的功能，既然是先让别人去做，得清楚的告诉他做什么。当前函数的功能，就是从head开始翻转链表，并返回翻转后的头节点
- 正式甩锅，进行递归调用
let newHead = reverseDigui(head.next)
原本是翻转以head开头的链表，可是不会啊，就交给下一个head.next去翻转。
- 根据别人的结果，计算自己的结果
第二步中，已经完成了从head.next开始翻转链表，那么，新链表的尾节点就是head.next, 现在，只需要把head连接到新链表中，head.next.next = head, 新链表的尾节点就变成head了。
- 找到递归终止条件
函数要返回新链表的头节点，新链表的头节点正是旧链表的尾节点，所以遇到尾节点时，递归就终止了
link6.png
function reserveDigui(head) {
if (!head) {
return null;
}
if (!head.next) { // 递归终止条件，返回值是新链表的头节点
return head;
}
let newHead = reserveDigui(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
- 合并两个有序链表
已知两个有序链表（元素从小到大），将两个链表合并成一个有序链表，并返回新链表，原有链表不要修改
思路分析：
- 如果两个链表中其中一个是空链表，直接返回不为空的那个就行了。
- 否则就设置一个循环，对当前的数值进行比较，小的那个放到新链表中，直到其中一个链表节点或者两个链表节点都是null时，结束循环
- 如果还有链表没到达尾节点，循环遍历添加到新链表中。
function mergeLink(head1, head2) {
if (!head1) {
return head2;
}
if (!head2) {
return head1;
}
let mergeHead = null; // 新链表头
let mergeTail = null; // 新链表尾
let curr1 = head1;
let curr2 = head2;
while(curr1 && curr2) {
let minData; // 记录最小值
if (curr1.data <curr2.data) {
minData = curr1.data;
curr1 = curr1.next;
} else {
minData = curr2.data;
curr2 = curr2.next;
}
if (!mergeHead) { // 头节点指向
mergeHead = new Node(minData);
mergeTail = mergeHead;
} else {
let newNode = new Node(minData);
mergeTail.next = newNode; // 添加新节点
mergeTail = newNode // 尾节点后移
}
}
let restLink = curr1 || curr2; // 还没到达尾节点的链表
while(restLink) { // 循环加进新链表中
let newNode = new Node(restLink.data);
mergeTail.next = newNode;
mergeTail = newNode;
restLink = restLink.next;
}
return mergeHead; // 返回新链表头
}
