概述
鏈表是物理存儲(chǔ)單元上非連續(xù)的山林、非順序的存儲(chǔ)結(jié)構(gòu)润脸，由一系列節(jié)點(diǎn)組成漠魏。
節(jié)點(diǎn)
節(jié)點(diǎn)包含兩部分倔矾，一部分是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，一部分是存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)的指針域。定義一個(gè)節(jié)點(diǎn)可以用如下代碼：
function Node (data) {
this.data = data;
this.next = null;
}
鏈表中的第一個(gè)節(jié)點(diǎn)是首節(jié)點(diǎn)哪自，最后一個(gè)節(jié)點(diǎn)是尾節(jié)點(diǎn)丰包。
有頭鏈表和無(wú)頭鏈表
無(wú)頭鏈表是指第一個(gè)節(jié)點(diǎn)既有數(shù)據(jù)域，又有指針域壤巷，第一個(gè)節(jié)點(diǎn)即是首節(jié)點(diǎn)又是頭節(jié)點(diǎn)邑彪。有頭鏈表是指第一個(gè)節(jié)點(diǎn)只有指針域，沒(méi)有數(shù)據(jù)域胧华。
有頭鏈表浪費(fèi)空間寄症，但是對(duì)于首個(gè)元素的操作（插入、刪除等）可以跟其他節(jié)點(diǎn)相同矩动，邊界好處理有巧。無(wú)頭鏈表節(jié)省空間，但是處理時(shí)要注意邊界情況悲没。這里使用的是無(wú)頭鏈表篮迎。
定義鏈表類：
function LinkList() {
// 定義節(jié)點(diǎn)
function Node (data) {
this.data = data;
this.next = null;
}
let length = 0; // 長(zhǎng)度
let head = null; // 頭節(jié)點(diǎn)
let tail = null; // 尾節(jié)點(diǎn)
}
給鏈表添加一些方法：
- append：添加一個(gè)新元素
- insert：在指定位置插入一個(gè)元素
- remove: 刪除指定位置的元素
- indexOf: 返回指定元素的索引
- get: 返回指定索引位置的元素
- isEmpty: 判斷鏈表是否為空
- print: 打印整個(gè)鏈表
function LinkList () {
// 定義節(jié)點(diǎn)
function Node (data) {
this.data = data;
this.next = null;
}
let length = 0; // 長(zhǎng)度
let head = null; // 頭節(jié)點(diǎn)
let tail = null; // 尾節(jié)點(diǎn)
this.append = function (data) { // 添加一個(gè)新元素
const node = new Node(data); // 創(chuàng)建一個(gè)新節(jié)點(diǎn)
if (!head) { // 如果是空鏈表，頭節(jié)點(diǎn)和尾節(jié)點(diǎn)都指向新節(jié)點(diǎn)
head = node;
tail = node;
} else {
tail.next = node; // 尾節(jié)點(diǎn)指向新創(chuàng)建的節(jié)點(diǎn)
tail = node; // tail指向最后一個(gè)節(jié)點(diǎn)
}
length++;
return true;
}
this.insert = function (index, data) { // 在指定位置插入一個(gè)元素
if (index < 0 || index > length) { // 范圍錯(cuò)誤
return false;
}
const node = new Node(data);
if (index === 0) { // 如果在頭節(jié)點(diǎn)前面插入示姿，新的節(jié)點(diǎn)就變成了頭節(jié)點(diǎn)
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; // 記錄要?jiǎng)h除的節(jié)點(diǎn)
if (index === 0) { // 如果刪除頭節(jié)點(diǎn)甜橱，head指向下一個(gè)節(jié)點(diǎn)
delNode = head;
head = head.next;
if (!head) { // 如果此時(shí)head是null，說(shuō)明之前只有一個(gè)節(jié)點(diǎn)栈戳，刪除之后變?yōu)榭真湵? tail = null; // 尾節(jié)點(diǎn)置空
}
} 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) { // 如果刪除的是尾節(jié)點(diǎn)岂傲，tail指向前一個(gè)節(jié)點(diǎn)
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) { // 有的話返回第一個(gè)
return index;
}
currentNode = currentNode.next;
}
return -1; // 如果沒(méi)有返回-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 () { // 打印整個(gè)鏈表
let currentNode = head;
while (currentNode) {
console.log(currentNode.data);
currentNode = currentNode.next;
}
}
}
之前用數(shù)組實(shí)現(xiàn)了棧和隊(duì)列，現(xiàn)在可以基于鏈表實(shí)現(xiàn)子檀。
為了實(shí)現(xiàn)方便譬胎，再給鏈表添加幾個(gè)方法：
this.head = function () { // 返回頭節(jié)點(diǎn)的值
return this.get(0);
}
this.tail = function () { // 返回尾節(jié)點(diǎn)的值
return this.get(length - 1);
}
this.removeHead = function () { // 刪除頭節(jié)點(diǎn)
return this.remove(0)
}
this.removeTail = function () { // 刪除尾節(jié)點(diǎn)
return this.remove(length - 1)
}
基于鏈表實(shí)現(xiàn)的棧：
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()
}
}
基于鏈表實(shí)現(xiàn)的隊(duì)列：
function Queue() {
let linkList = new LinkList();
this.enqueue = function (item) { // 入隊(duì)列
linkList.append(item);
}
this.dequeue = function () { // 出隊(duì)列
return linkList.removeHead();
}
this.head = function () { // 返回隊(duì)首元素
return linkList.head();
}
this.tail = function () { // 返回隊(duì)尾元素
return linkList.tail();
}
}
練習(xí)題
一、翻轉(zhuǎn)鏈表
翻轉(zhuǎn)之前：
翻轉(zhuǎn)之后：
1命锄、迭代翻轉(zhuǎn)
假設(shè)有三個(gè)節(jié)點(diǎn)的一個(gè)鏈表堰乔，我們?cè)O(shè)preNode指向前一個(gè)節(jié)點(diǎn), currentNode指向是當(dāng)前要翻轉(zhuǎn)的節(jié)點(diǎn)，在當(dāng)前節(jié)點(diǎn)進(jìn)行翻轉(zhuǎn)：
currentNode.next = preNode;
在遍歷過(guò)程中脐恩，每完成一個(gè)節(jié)點(diǎn)的翻轉(zhuǎn)镐侯，都讓currentNode = nextNode，指向下一個(gè)要翻轉(zhuǎn)的節(jié)點(diǎn)驶冒，preNode和nextNode也一起向后滑動(dòng)苟翻。
對(duì)于頭節(jié)點(diǎn)來(lái)說(shuō)，它翻轉(zhuǎn)過(guò)后就是尾節(jié)點(diǎn)，尾節(jié)點(diǎn)的next指向null，所以初始化preNode = null;
function reverseIter(head) {
if (!head) { // 如果是空鏈表泛范，直接返回
return null;
}
let preNode = null; // 前一個(gè)節(jié)點(diǎn)
let currentNode = head; // 當(dāng)前要翻轉(zhuǎn)的節(jié)點(diǎn)
while(currentNode) {
let nextNode = currentNode.next; // 記錄下一個(gè)節(jié)點(diǎn)
currentNode.next = preNode; // 翻轉(zhuǎn)當(dāng)前節(jié)點(diǎn)，讓他指向前一個(gè)節(jié)點(diǎn)
preNode = currentNode; // 后移
currentNode = nextNode;
}
return preNode; // 返回翻轉(zhuǎn)之后的頭節(jié)點(diǎn)
}
- 遞歸翻轉(zhuǎn)
看視頻時(shí)聽張老師說(shuō)遞歸的精髓在于甩鍋诅炉，你做不到的事情蜡歹，讓別人去做，等別人做完了涕烧，你在別人的基礎(chǔ)上繼續(xù)做月而。我覺(jué)得總結(jié)的很精辟。
- 首先明確函數(shù)的功能议纯，既然是先讓別人去做父款，得清楚的告訴他做什么。當(dāng)前函數(shù)的功能瞻凤，就是從head開始翻轉(zhuǎn)鏈表憨攒，并返回翻轉(zhuǎn)后的頭節(jié)點(diǎn)
- 正式甩鍋，進(jìn)行遞歸調(diào)用
let newHead = reverseDigui(head.next)
原本是翻轉(zhuǎn)以head開頭的鏈表阀参，可是不會(huì)啊肝集，就交給下一個(gè)head.next去翻轉(zhuǎn)。
- 根據(jù)別人的結(jié)果结笨，計(jì)算自己的結(jié)果
第二步中，已經(jīng)完成了從head.next開始翻轉(zhuǎn)鏈表湿镀，那么炕吸，新鏈表的尾節(jié)點(diǎn)就是head.next, 現(xiàn)在，只需要把head連接到新鏈表中勉痴，head.next.next = head, 新鏈表的尾節(jié)點(diǎn)就變成head了赫模。
- 找到遞歸終止條件
函數(shù)要返回新鏈表的頭節(jié)點(diǎn)，新鏈表的頭節(jié)點(diǎn)正是舊鏈表的尾節(jié)點(diǎn)蒸矛，所以遇到尾節(jié)點(diǎn)時(shí)瀑罗，遞歸就終止了
function reserveDigui(head) {
if (!head) {
return null;
}
if (!head.next) { // 遞歸終止條件，返回值是新鏈表的頭節(jié)點(diǎn)
return head;
}
let newHead = reserveDigui(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
- 合并兩個(gè)有序鏈表
已知兩個(gè)有序鏈表（元素從小到大）雏掠，將兩個(gè)鏈表合并成一個(gè)有序鏈表斩祭，并返回新鏈表，原有鏈表不要修改
思路分析：
- 如果兩個(gè)鏈表中其中一個(gè)是空鏈表乡话，直接返回不為空的那個(gè)就行了摧玫。
- 否則就設(shè)置一個(gè)循環(huán)，對(duì)當(dāng)前的數(shù)值進(jìn)行比較绑青，小的那個(gè)放到新鏈表中诬像，直到其中一個(gè)鏈表節(jié)點(diǎn)或者兩個(gè)鏈表節(jié)點(diǎn)都是null時(shí)，結(jié)束循環(huán)
- 如果還有鏈表沒(méi)到達(dá)尾節(jié)點(diǎn)闸婴，循環(huán)遍歷添加到新鏈表中坏挠。
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) { // 頭節(jié)點(diǎn)指向
mergeHead = new Node(minData);
mergeTail = mergeHead;
} else {
let newNode = new Node(minData);
mergeTail.next = newNode; // 添加新節(jié)點(diǎn)
mergeTail = newNode // 尾節(jié)點(diǎn)后移
}
}
let restLink = curr1 || curr2; // 還沒(méi)到達(dá)尾節(jié)點(diǎn)的鏈表
while(restLink) { // 循環(huán)加進(jìn)新鏈表中
let newNode = new Node(restLink.data);
mergeTail.next = newNode;
mergeTail = newNode;
restLink = restLink.next;
}
return mergeHead; // 返回新鏈表頭
}
