# 链表
# 1、概念
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的；简单来说，线性表的链式存储结构生成的表，称作“链表”。链表中每个数据元素都由两部分组成：1、本身的信息，称为“数据域”；2、指向直接后继的指针，称为“指针域”。这两部分信息组成数据元素的存储结构，称之为“结点”；n个结点通过指针域相互链接，组成一个链表。
逻辑结构上一个挨一个的数据，在实际存储时，并没有像顺序表那样也相互紧挨着。恰恰相反，数据随机分布在内存中的各个位置，这种存储结构称为线性表的链式存储。
由于分散存储，为了能够体现出数据元素之间的逻辑关系，每个数据元素在存储的同时，要配备一个指针，用于指向它的直接后继元素，即每一个数据元素都指向下一个数据元素（最后一个指向NULL）。
# 2、头结点、头指针和首元结点
头结点：有时，在链表的第一个结点之前会额外增设一个结点，结点的数据域一般不存放数据（有些情况下也可以存放链表的长度等信息），此结点被称为头结点。
若头结点的指针域为空（NULL），表明链表是空表。头结点对于链表来说，不是必须的，在处理某些问题时，给链表添加头结点会使问题变得简单。
首元结点：链表中第一个元素所在的结点，它是头结点后边的第一个结点。
头指针：永远指向链表中第一个结点的位置（如果链表有头结点，头指针指向头结点；否则，头指针指向首元结点）。
头结点和头指针的区别：头指针是一个指针，头指针指向链表的头结点或者首元结点；头结点是一个实际存在的结点，它包含有数据域和指针域。两者在程序中的直接体现就是：头指针只声明而没有分配存储空间，头结点进行了声明并分配了一个结点的实际物理内存。
优缺点
使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。线性表的链式存储表示，有一个缺点就是要找一个数，必须要从头开始找起，十分麻烦。
链表的算法题也比较多，主要就是要理清楚思路再去做。
# 3、基础操作
链表的增删
function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
/* 创建一个链表 */
function createLinkedList(arr) {
if (arr.length === 0) return null;
const head = new ListNode(arr[0]);
let pointer = head;
for (let i = 1; i < arr.length; i++) {
const newNode = new ListNode(arr[i]);
pointer.next = newNode;
pointer = newNode;
}
return head;
}
function printLinkedList(head) {
let pointer = head;
let str = '';
while (pointer) {
str = str + pointer.val + '->';
pointer = pointer.next;
}
str += 'null';
console.log(str);
}
# 3.1 往一个有序的链表插入节点
function insertIntoSortedLinked(link, newNode) {
if (!link) {
return newNode;
}
let p = link;
let head = link;
let preNode = null;
while (p) {
if (newNode.val < p.val) {
if (!preNode) {
// 还不存在前置节点， 说明需要插入第一位
newNode.next = p;
return newNode;
} else {
// 说明需要插入中间
newNode.next = p;
preNode.next = newNode;
return head;
}
}
preNode = p;
p = p.next;
}
// 如果上述没有返回 说明需要插入尾部， 此时的preNode保存的就是最后一个节点
if (preNode) {
preNode.next = newNode;
}
return head;
}
# 3.2 反转一个链表
function reverseLinkedList(link) {
if (!link) {
return link;
}
let pre = null,
p = link;
while (p) {
let next = p.next; // 先获取到下一个节点
p.next = pre; // 此时p.next 这个指向已经无用了， 可以重置为上一个节点
// 此时完成了反转，开始循环下下一个节点
pre = p;
p = next;
}
return pre;
}
# 3.3 删除节点
删除第一个符合条件的节点
function deleteOneNode(link, node, predicate) {
let pre = null;
let p = link;
let head = link;
while (p) {
if (predicate(p, node)) {
// 满足判断函数即删除
if (!pre) {
// 说明删除的是第一个
head = p.next;
break;
} else {
pre.next = p.next;
break;
}
}
pre = p;
p = p.next;
}
return head;
}
// printLinkedList(deleteOneNode(link, new LinkedNode(3), (a, b) => a.val === b.val));
删除所有符合条件的节点
function deleteMultiNode(link, node, predicate) {
let pre = null;
let p = link;
let head = link;
while (p) {
if (predicate(p, node)) {
// 满足判断函数即删除
if (!pre) {
// 说明删除的是第一个
head = p.next;
pre = null;
p = p.next;
continue;
} else {
pre.next = p.next;
p = p.next;
continue;
}
}
pre = p;
p = p.next;
}
return head;
}
const link = createLinkedList([2, 2, 1, 2, 2, 4, 2, 3]);
printLinkedList(link);
printLinkedList(deleteMultiNode(link, new LinkedNode(2), (a, b) => a.val <= b.val));
删除链表里面的重复元素
var deleteDuplicates = function (head) {
let p = head;
let preNode = null;
const recordSet = new Set();
while (p) {
const val = p.val;
const next = p.next;
if (recordSet.has(val)) {
if (preNode) {
preNode.next = next;
p = next;
continue;
}
} else {
recordSet.add(val);
preNode = p;
p = next;
}
}
return head;
};
# 3.4 合并2个有序链表
// leetcode 21
function mergeTwoLists(l1, l2) {
const head = new LinkedNode();
let p = head;
let curNode1 = l1;
let curNode2 = l2;
while (curNode1 || curNode2) {
const newNode = new LinkedNode();
p.next = newNode;
p = newNode;
if (curNode1 && curNode2) {
if (curNode1.val === curNode2.val) {
p.val = curNode1.val;
const newNode = new LinkedNode(curNode2.val);
p.next = newNode;
p = newNode;
curNode1 = curNode1.next;
curNode2 = curNode2.next;
} else if (curNode1.val > curNode2.val) {
p.val = curNode2.val;
curNode2 = curNode2.next;
} else if (curNode1.val < curNode2.val) {
p.val = curNode1.val;
curNode1 = curNode1.next;
}
} else if (curNode1 && !curNode2) {
p.val = curNode1.val;
curNode1 = curNode1.next;
} else if (curNode2 && !curNode1) {
p.val = curNode2.val;
curNode2 = curNode2.next;
}
}
return head.next;
}
const link1 = createLinkedList([1, 3, 5, 7]);
const link2 = createLinkedList([1, 4, 9, 12]);
printLinkedList(mergeTwoLists(link1, link2))
# 3.5 相加2个链表
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
// leetcode 2
var addTwoNumbers = function (l1, l2) {
let p1 = l1;
let p2 = l2;
let carryBit = 0; // 需要考虑大于10的进位
let head = new ListNode();
let p = head;
while (p1 || p2) {
let val1 = p1.val || 0;
let val2 = p2.val || 0;
let sum = val1 + val2 + carryBit;
let val;
if (sum >= 10) {
carryBit = 1;
val = sum % 10;
} else {
carryBit = 0;
val = sum;
}
p.val = val;
p1 = p1 ? p1.next : null;
p2 = p2 ? p2.next : null;
if (p1 || p2) {
// 说明还存在下一个
const newNode = new ListNode();
p.next = newNode;
p = newNode;
}
}
// 说明最后一位是1, 比如这种情况 [1, 2] + [2, 8] = [3, 0, 1], 21 + 82 = 103
if (carryBit === 1) {
const newNode = new ListNode(1);
p.next = newNode;
p = newNode;
}
return head;
};
const link1 = createLinkedList([1, 3, 5, 7]);
const link2 = createLinkedList([1, 4, 9, 4]);
printLinkedList(addTwoNumbers(link1, link2));
# 3.6 交换相邻的2个元素
[1, 2, 3, 4] => [2, 1, 4, 3]
// leetcode 24
var swapPairs = function (head) {
if (!head) {
return null;
}
if (head.next === null) {
return head;
}
let p1 = head;
let p2 = p1.next;
let pre = null;
let newHead = p2;
while (p1 && p2) {
let next = p2.next;
p2.next = p1;
p1.next = next;
if (pre) {
pre.next = p2;
}
pre = p1;
p1 = next;
if (p1) {
p2 = p1.next;
} else {
p2 = null;
}
}
return newHead;
};
# 3.7 判断一个链表是否有环
// 记录遍历过的值
function isLoopLinked(link) {
let p = link;
const map = new Map();
map.set(p, true);
while (p) {
p = p.next;
if (map.get(p)) {
return true;
} else {
map.set(p, true);
}
}
return false;
}
// 快慢指针， 如果有环， 快的会追上慢的
function isLoopLinked2(link) {
let p1 = link;
let p2 = link;
while (p1 && p2) {
p1 = p1.next;
p2 = p2 && p2.next ? p2.next.next : null;
if (p1 === p2) {
return true;
}
}
return false;
}