Keep coding , Keep learning .
一、基本概念
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链表的入口节点称为链表的头结点也就是head。
二、链表的类型
-
单链表
单链表中的指针域只能指向节点的下一个节点。
-
双链表
每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
-
循环链表
链表首尾相连
循环链表可以用来解决约瑟夫环问题。
三、链表的声明
class ListNode {
val;
next = null;
constructor(value) {
this.val = value;
this.next = null;
}
}
四、性能分析
链表特性和数组特性对比
| 插入/删除（时间复杂度） | 查询（时间复杂度） | 适用场景 | |
| 数组 | O(n) | O(1) | 数据量固定，频繁查询，较少增删 |
| 链表 | O(1) | O(n) | 数据量不固定，频繁增删，较少查询 |
五、例题
链表操作的两种方式：
- 直接使用原来的链表来进行操作。
- 设置一个虚拟头结点在进行操作。
class ListNode {
val;
next = null ;
constructor(value){
this.val = value;
this.next = null;
}
}
1. 移除链表元素
链表操作的两种方式：
-
直接使用原来的链表来进行删除操作。
- 若是移除头节点 - 将头结点向后移动一位
- 若是移除其它节点 - 通过前一个节点来移除当前节点
-
设置一个虚拟头结点在进行删除操作。
- 设置虚拟头结点
- 移除其它节点
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
// 定义虚拟头结点
const newHead = new ListNode(0,head)
// 移除其它节点
let cur = newHead
while(cur.next){
// 是否存在下一节点
if(cur.next.val === val){
// 移除下一个节点
cur.next = cur.next.next
} else {
cur = cur.next
}
}
return newHead.next
};
2. 设计链表
要实现链表的五个接口功能：
- 获取链表第
index个节点的数值 - 在链表的最前面插入一个节点
- 在链表的最后面插入一个节点
- 在链表第
index个节点前面插入一个节点 - 删除链表的第
index个节点
class LinkNode {
constructor(val, next) {
this.val = val;
this.next = next;
}
}
class MyLinkedList {
//单链表
constructor(){
// 存储节点数量
this._size = 0
// 存储头尾节点
this._head = null
this._tail = null
}
getNode(index){
if(index < 0 || index >= this._size) return null;
// 创建虚拟头节点
let cur = new LinkNode(0, this._head);
// 0 -> head
while(index-- >= 0) {
cur = cur.next;
}
return cur;
}
get(index){
if(index < 0 || index >= this._size) return -1;
// 获取当前节点
return this.getNode(index).val;
}
addAtHead(val){
const node = new LinkNode(val, this._head);
this._head = node;
this._size++;
if(!this._tail) {
this._tail = node;
}
}
addAtTail(val){
const node = new LinkNode(val, null);
this._size++;
if(this._tail) {
this._tail.next = node;
this._tail = node;
return;
}
this._tail = node;
this._head = node;
}
addAtIndex(index,val){
if(index > this._size) return;
if(index <= 0) {
this.addAtHead(val);
return;
}
if(index === this._size) {
this.addAtTail(val);
return;
}
// 获取目标节点的上一个的节点
const node = this.getNode(index - 1);
node.next = new LinkNode(val, node.next);
this._size++;
}
deleteAtIndex(index){
if(index < 0 || index >= this._size) return;
if(index === 0) {
this._head = this._head.next;
// 如果删除的这个节点同时是尾节点，要处理尾节点
if(index === this._size - 1){
this._tail = this._head
}
this._size--;
return;
}
// 获取目标节点的上一个的节点
const node = this.getNode(index - 1);
node.next = node.next.next;
// 处理尾节点
if(index === this._size - 1) {
this._tail = node;
}
this._size--;
}
}
3. 反转链表
** 思路**：
-
定义一个新的链表，实现链表元素的翻转，但这是对内存空间的浪费。
-
改变原链表的
next指针的指向，直接将链表反转。- 定义两个指针，
cur指向当前节点，初始时为head；pre指向cur的前一节点，初始时为null - 反转过程就是一次变量赋值的交换，使原来的
cur.next的指向pre，需要先使用temp保存一下cur.next，然后改变cur.next = pre，使其指向pre。 - 继续移动指针
cur，而cur的下一个位置就是上一次的cur.next，所以将temp保存的cur.next赋值给cur即可。 - 最后，当
cur指针已经指向了null代表循环结束，链表反转完毕。
- 定义两个指针，
var reverseList = function(head) {
if(!head || !head.next) return head;
let temp = null
let pre = null
let cur = head
while(cur){
temp = cur.next
cur.next = pre
pre = cur
cur = temp
}
return pre
};
4. 两两交换链表中的节点
var swapPairs = function(head) {
let ret = new ListNode(0, head)
let temp = ret
while (temp.next && temp.next.next) {
let cur = temp.next.next
pre = temp.next
pre.next = cur.next
cur.next = pre
temp.next = cur
temp = pre
}
return ret.next;
};
