单链表问题
单链表节点定义
class Node {
public ele: any;
public next: null;
constructor(ele) {
this.ele = ele;
this.next = null;
}
}2. 单链表基本操作
插入 `insert(ele, pos)`
查询 `get(pos)`
删除 `remove(pos)`
获取头节点 `getHead()`
获取链表长度 `getSize()`
判断链表是否为空 `isEmpty()`
获取链表节点数组 `getList()`
3. 基本操作实现
class LinkedList {
private head: any;
private length: number;
constructor() {
this.head = null;
this.length = 0;
}
/**
* 查询指定位置节点
* @param pos 待搜索节点位置
* @returns {Node} 找到返回节点,否则返回-1
*/
get(pos) {
if (pos < 0 || pos > this.length) {
console.warn("索引位置非法！");
return -1;
}
let tmp = this.head,
index = 0;
while (index++ < pos) {
tmp = tmp.next;
}
return tmp;
}
/**
* 追加节点
* @param {Node} ele 待插入节点
* @returns {Boolean} 插入成功返回true，否则false
*/
append(ele) {
let newNode = new Node(ele);
if (!this.head) {
this.head = newNode;
} else {
let tmp = this.head;
while (tmp.next) {
tmp = tmp.next;
}
tmp.next = newNode;
}
this.length++;
return true;
}
/**
* 指定位置插入节点
* @param {Node} ele 待插入节点
* @param {Number} pos 待插入位置 默认为length
* @returns {Boolean} 插入成功返回true，否则false
*/
insert(ele, pos?) {
let validPos = pos ?? this.length; // pos为null/undefined是取右边的值
if (validPos < 0 || validPos > this.length) {
console.warn("插入位置非法！");
return false;
}
let newNode = new Node(ele),
tmp = this.head,
index = 0,
prev;
if (validPos == 0) {
newNode.next = tmp;
// 更新头节点
this.head = newNode;
} else {
while (index++ < validPos) {
prev = tmp;
tmp = tmp.next;
}
// console.log('test', prev, tmp);
// newNode要插在prev和tmp之间
// newNode下一个指向tmp
// prev下一个指向newNode
// 从而把链条拼接上
newNode.next = tmp;
prev.next = newNode;
}
this.length++;
return true;
}
/**
* 指定位置删除节点
* @param {Number} pos 待删除位置
* @returns {Boolean} 删除成功返回true，否则false
*/
remove(pos) {
if (pos < 0 || pos > this.length) {
console.warn("删除位置非法！");
return false;
}
// 找到要删除节点以及其之前的节点
let tmp = this.head,
index = 0,
prev;
if (pos === 0) {
this.head = this.head.next;
} else {
while (index++ < pos) {
prev = tmp;
tmp = tmp.next;
}
// console.log('test', prev, tmp);
// 直接跳过tmp,和tmp的下一个节点拼接
prev.next = tmp.next;
}
this.length--;
return true;
}
/**
* 链表是否为空
* @returns {Boolean} 链表为空返回true,否则false
*/
isEmpty() {
return this.length === 0;
}
/**
* 获取头节点
* @returns {Node} 返回头节点
*/
getHead() {
return this.head;
}
/**
* 获取链表长度
* @returns {Number} 返回链表长度
*/
getSize() {
return this.length;
}
/**
* 获取链表元素数组
* @returns {Array} 返回链表元素数组
*
* TODO 需要考虑环状链表
*/
getList() {
const ret = [];
let cur = this.head;
while (cur.next) {
ret.push(cur.ele);
cur = cur.next;
}
ret.push(cur.ele);
return ret;
}
}4. 单链表高级操作
4. 1 链表合并
将两个升序链表合并为一个新的升序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成的
const mergeTwoList = (r1, r2) => {
if (r1 === null) return r2;
if (r2 === null) return r1;
if (r1.ele <= r2.ele) {
// 指针后移
r1.next = mergeTwoList(r1.next, r2)
return r1
} else {
r2.next = mergeTwoList(r2.next, r1)
return r2
}
}4. 2 链表环检测
给定一个链表，判断链表中是否有环
方法1： 标记法
遍历链表，给已遍历过的节点加标志位
const hasCycle = (r) => {
while (r) {
if (r.visited) return true
r.visited = true
r = r.next;
}
return false
}方法2：`JSON.stringify`
`JSON.stringify`序列化含有循环引用结构会报错
const hasCycle = (r) => {
try {
JSON.stringify(r);
return false
} catch (e) {
return true
}
}方法3：双指针
快慢指针: 遍历单链表，快指针一次走两步，慢指针一次走一步
如果单链表中存在环，则快慢指针终会指向同一个节点，否则直到快指针指向 null 时，快慢指针都不可能相遇
const hasCycle = (r) => {
if (!r || !r.next) return false
let fast = r.next.next, slow = r.next;
while (fast !== slow) {
if (!fast || !fast.next) return false
fast = fast.next.next
slow = slow.next
}
// 如需找到环入口只需新建一个指针tmp和slow指针同时向前遍历，当两者相等时，入口就是tmp
return true
}4.3 链表中间元素
求链表的中间结点，节点个数为偶数2n时返回n+1所在节点
快慢指针: 遍历单链表，快指针一次走两步，慢指针一次走一步
快指针走到尾节点的时候就是满指针走到中间的时候
const getMiddle = (r) => {
if (!r || !r.next) return r;
let fast = r, slow = r;
while (fast && fast.next) {
fast = fast.next.next;
slow = slow.next
}
return slow
}4.4 链表反转
方法1： 迭代法(三指针法)
使用三个指针prev, cur和next实现
next在遍历链表的时候临时保存cur的下一个节点
prev初始值为null，遍历链表的时候反转cur的指向到prev
prev和cur分别前移
const reverse = (r) => {
if (!r || !r.next) return r;
let prev = null, cur = r;
while (cur) {
// 用于临时存储 cur 后继节点
// 否则下一步就会抹掉原来的cur.next
let next = cur.next; // 4
// 反转 cur 的后继指针
cur.next = prev; // 首个节点的next就变为了null
// 变更prev、cur
prev = cur; // prev前移
cur = next // cur前移
}
r = prev;
return r;
}方法2： 递归
const reverse = (r) => {
const _reverse = function (prev, cur) {
if (!cur) return prev // 前移的时候cur为null就结束了
// 临时存储
let next = cur.next;
// 核心反转
cur.next = prev;
return _reverse(cur, next) // prev,cur => cur, next
}
if (!r || !r.next) return r;
r = _reverse(null, r);
return r;
}4.5 链表求和
给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。
const addTwoNumbers = (l1, l2) => {
let carry = 0;
let head = null, tail = null; // 当carry>0时，tail用于表示进位
while (l1 || l2) {
let n1 = l1 ? l1.ele : 0;
let n2 = l2 ? l2.ele : 0;
let sum = n1 + n2 + carry;
if (!head) {
head = tail = new Node(sum % 10);
} else {
tail.next = new Node(sum % 10);
tail = tail.next
}
carry = (sum / 10) >> 0
// console.log('ele', sum, l1.ele, l2.ele)
if (l1) {
l1 = l1.next;
}
if (l2) {
l2 = l2.next;
}
}
// 如果有进位，附加一个新节点，其值为carry
if (carry) {
tail.next = new Node(carry)
}
return head
}4.6 回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。
方法1：遍历链表将节点值放入数组，然后双指针 复杂度：O(n) O(n)
var isPalindrome = function (head) {
const arr = [];
while (head) {
arr.push(head.val);
head = head.next;
}
let i = 0,
len = arr.length,
j = len - 1;
for (i, j; i < j; i++, j--) {
if (arr[i] !== arr[j]) {
return false;
}
}
return true;
};方法2：前半部分指针反转一下，然后再判断回文 复杂度：O(n) O(1)
var isPalindrome = function (head) {
let slow = head,
fast = head;
let prev = null,
next = null;
while (fast !== null && fast.next !== null) {
fast = fast.next.next;
next = slow.next;
// slow 边走边逆序
slow.next = prev;
prev = slow;
slow = next;
}
if (fast !== null) {
// 链表长度为奇数
slow = slow.next;
}
while (prev !== null && slow !== null) {
if (prev.val !== slow.val) {
return false;
}
prev = prev.next;
slow = slow.next;
}
return true;
};4.7 链表排序
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
var sortList = function (head) {
// 自顶向下归并排序
// 1. 找到链表的中点，以中点为分界，将链表拆分成两个子链表。
// 寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点
// 2. 对两个子链表分别排序。
// 3. 将两个排序后的子链表合并，得到完整的排序后的链表
return toSortList(head, null);
};
var toSortList = function (head, tail) {
if (!head || !head.next) {
return head;
}
if (head.next === tail) {
head.next = null;
return head;
}
// let slow = head.next;
// let fast = head.next.next;
// while (fast && fast.next && fast !== tail) {
// slow = slow.next;
// fast = fast.next.next;
// }
let slow = head,
fast = head;
while (fast !== tail) {
slow = slow.next;
fast = fast.next;
if (fast !== tail) {
fast = fast.next;
}
}
const mid = slow;
return mergeTwoList(toSortList(head, mid), toSortList(mid, tail));
};
Last updated