本文首发于我的Github
链表存储有序的元素集合,但不同于数组,链表中的元素在内存中不是连续放置的。每个元素由一个存储元素本身的节点和指向下一个元素的 引用 组成。
------------------------------------------------------------------------
| |
| node node null |
| --------------- --------------- -------- |
| head -> + item | next + -> + item | next + -> + null + |
| --------------- --------------- -------- |
| |
------------------------------------------------------------------------
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkList {
constructor() {
this.head = null;
this.length = 0;
}
/**
* 添加节点
* @param {*} value
*/
append(value) {
return this.insert(value, this.length);
}
/**
* 添加节点到指定位置
* @param {*} value
* @param {*} position
*/
insert(value, position) {
if (position < 0 || position > this.length) {
return false;
}
let node = new Node(value);
if (position === 0) {
node.next = this.head;
this.head = node;
} else {
let prev = null;
let current = this.head;
let i = 0;
while (i++ < position) {
prev = current;
current = current.next;
}
prev.next = node;
node.next = current;
}
this.length++;
return true;
}
/**
* 移出指定位置的节点
* @param {*} position
*/
removeAt(position) {
if (position < 0 || position > this.length) {
return false;
}
if (position === 0) {
this.head = this.head.next;
} else {
let prev = null;
let current = this.head;
let i = 0;
while (i++ < position) {
prev = current;
current = current.next;
}
prev.next = current.next;
}
this.length--;
return true;
}
/**
* 查找给定值所在索引
* @param {*} value
*/
indexOf(value) {
let current = this.head;
let index = -1;
while (current) {
indeex++;
if (current.value === value) {
return index;
} else {
current = current.next;
}
}
return -1;
}
reverse() {
let prev = null;
let current = this.head;
let next = null;
while (current) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
this.head = prev;
}
traverseFromTailToHead() {
let stack = [];
let current = this.head;
while (current) {
stack.push(current);
current = current.next;
}
while (stack.length) {
stack.pop();
}
}
getKthNodeFromTailToHead(k) {
let p1 = this.head;
let p2 = this.head;
let i = 0;
while (i++ < k) {
p1 = p1.next;
}
while (p1) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
}
题目
1. 输出单链表倒数第 k 个节点
问题描述
题目:输入一个单链表,输出此链表中的倒数第 K 个节点。(去除头结点,节点计数从 1 开始)。
解题思路
倒数第 k 个节点即为整数第 n - k 个节点(n 为链表长度)
- 定义 2 个指针同时执行链表头节点
- 第 1 个指针前进 k 个 节点
- 两个指针同时前进,当第 1 个指针到达链表尾时,第 2 个指针与第一个指针相距 k 个节点,第二个指指向节点即为所求
function findKthTail(linkList, k) {
let p1 = linkList.head;
let p2 = linkList.head;
let i = 0;
while (i++ < k) {
p1 = p1.next;
}
while (p1) {
p1 = p1.next;
p2 = p2.next;
}
return p2;
}
2. 判断链表是否有环
问题描述
单链表中的环是指链表末尾的节点的 next 指针不为 NULL ,而是指向了链表中的某个节点,导致链表中出现了环形结构。
0 -> 1 -> 2 -> 3 -> 4
| |
6 <- 5
链表中尾节点 6
指向了 节点 3
而非 null
,导致出现了环形结构。
解题思路
- 定义 2 个快慢指针,初始均指向头节点
- 第 1 个指针前进 1 步,第 2 个指针前进 2 步
- 若是无环,2 个指针最后均指向
null
,但若是有环,2 指针必定在一个节点处相遇,该节点不为null
/**
* 判断链表是否存在环
* @param {*} linkList
*/
function isExistLoop(linkList) {
let p1 = linkList.head;
let p2 = linkList.head;
while (p1 && p2.next) {
p1 = p1.next;
p2 = p2.next.next;
if (p1 === p2) {
return true;
}
}
return false;
}
问题描述
定位环的起点。
解题思路
定义2个快慢指针,第一次先找到 2 个指针在环中的相遇点,然后令 p1 指向 相遇点,p2 指向头节点,同时出发(每次走过的节点相同),当 2 指针指向的节点相同时,p1 即为环的起点。
function getMeetingNode(linkList) {
let p1 = linkList.head;
let p2 = linkList.head;
while (p1 && p2.next) {
p1 = p1.next;
p2 = p2.next.next;
if (p1 == p2) {
return p1;
}
}
return null;
}
function getEntryOfLoop(linkList) {
let meetingNode = linkList.getMeetingNode();
if (!meetingNode) {
return null;
}
let p1 = meetingNode;
let p2 = linkList.head;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}