链表
details
class LinkNode {
constructor(val, next = null) {
this.value = val;
this.next = next;
}
}
class LinkedList {
constructor() {
this.head = null;
}
insert(val) {
if (this.head === null) {
this.head = new LinkNode(val);
return;
}
// find the last node
let current = this.head;
while (current.next !== null) {
current = current.next;
}
// next pointer to the new node
current.next = new LinkNode(val);
}
delete(val) {
if (!this.head) return;
// head
if (this.head.value === val) {
this.head = this.head.next;
return;
}
let current = this.head;
while (current.next !== null && current.next.value !== val) {
current = current.next;
}
// middle
if (current.next !== null) {
current.next = current.next.next;
}
// tail
}
find(val) {
let current = this.head;
while (current !== null) {
if (current.value === val) {
return current;
}
current = current.next;
}
return null;
}
toArray() {
const result = [];
let current = this.head;
while (current !== null) {
result.push(current.value);
current = current.next;
}
return result;
}
}
function traverse_linear(head) {
const result = [];
let current = head;
while (current !== null) {
result.push(current.value);
current = current.next;
}
return result;
}
function traverse_linear_for(head) {
const result = [];
for (let node = head; node !== null; node = node.next) {
result.push(node.value);
}
return result;
}
function traverse_recursive(head) {
let result = [];
traverse(head);
function traverse(node) {
if (!node) return;
result.push(node.value);
traverse(node.next);
}
return result;
}
142. 环形链表 II
HashSet
HashSet 缓存遍历过的节点
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
const visited = new Set();
while (head !== null) {
if (visited.has(head)) {
return head;
}
visited.add(head);
head = head.next;
}
return null;
};
快慢指针
相遇点,快指针比慢指针多走了一倍的路程。相当于从起点到入环的距离等于相遇点到入环的距离,因此,可以定义一个新指针 p 从 head 开始走,slow 跟 p 相遇的时候就是环起点。
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
if (!head || !head.next) return null;
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
let start = head;
while (start !== slow) {
start = start.net;
slow = slow.next;
}
return start;
}
}
return null; // 没有环
};
141. 环形链表
快慢指针
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var hasCycle = function (head) {
if (!head || !head.next) return false;
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true; // 环存在
}
}
return false; // 没有环
};
202. 快乐数
hash 表
Javascript
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function (n) {
const visited = new Set();
while (n !== 1 && !visited.has(n)) {
visited.add(n);
n = getNext(n);
}
return n === 1;
function getNext(n) {
let sum = 0;
while (n > 0) {
let d = n % 10;
n = (n / 10) >> 0;
sum += d ** 2;
}
return sum;
}
};
快慢指针
Javascript
/**
* @param {number} n
* @return {boolean}
*/
var isHappy = function (n) {
let slow = n,
fast = getNext(n);
while (fast !== 1 && slow !== fast) {
slow = getNext(slow);
fast = getNext(getNext(fast));
}
return fast === 1;
function getNext(n) {
let sum = 0;
while (n > 0) {
let d = n % 10;
n = (n / 10) >> 0;
sum += d ** 2;
}
return sum;
}
};
206. 反转链表
迭代
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function (head) {
if (head === null) return head;
let cur = head,
prev = null;
while (cur !== null) {
let next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return prev;
};
递归
Javascript
var reverseList = function (head) {
return traverse(head, null);
function traverse(cur, prev) {
if (cur === null) return prev;
let next = cur.next;
cur.next = prev;
return traverse(next, cur);
}
};
92. 反转链表 II
Javascript
var reverseBetween = function (head, left, right) {
// 因为头节点有可能发生变化,使用虚拟头节点可以避免复杂的分类讨论
const dummyNode = new ListNode(-1);
dummyNode.next = head;
let pre = dummyNode;
// 第 1 步:从虚拟头节点走 left - 1 步,来到 left 节点的前一个节点
// 建议写在 for 循环里,语义清晰
for (let i = 0; i < left - 1; i++) {
pre = pre.next;
}
// 第 2 步:从 pre 再走 right - left + 1 步,来到 right 节点
let rightNode = pre;
for (let i = 0; i < right - left + 1; i++) {
rightNode = rightNode.next;
}
// 第 3 步:切断出一个子链表(截取链表)
let leftNode = pre.next;
let curr = rightNode.next;
// 注意:切断链接
pre.next = null;
rightNode.next = null;
// 第 4 步:同第 206 题,反转链表的子区间
reverseLinkedList(leftNode);
// 第 5 步:接回到原来的链表中
pre.next = rightNode;
leftNode.next = curr;
return dummyNode.next;
};
const reverseLinkedList = head => {
let pre = null;
let cur = head;
while (cur) {
const next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
};
1019. 链表中的下一个更大节点
单调栈
Javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* @param {ListNode} head
* @return {number[]}
*/
var nextLargerNodes = function (head) {
const stack = [];
const result = [];
let i = 0;
while (head) {
result.push(0);
while (stack.length && stack[stack.length - 1].val < head.val) {
const node = stack.pop();
result[node.index] = head.val;
}
stack.push({ val: head.val, index: i });
i++;
head = head.next;
}
return result;
};
Rust
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
pub val: i32,
pub next: Option<Box<ListNode>>,
}
impl ListNode {
#[inline]
fn new(val: i32) -> Self {
ListNode { next: None, val }
}
}
struct Solution {}
impl Solution {
fn next_larger_nodes(head: Option<Box<ListNode>>) -> Vec<i32> {
let mut result = Vec::new();
let mut stack = Vec::new();
let mut current = &head;
while let Some(node) = current {
while !stack.is_empty() && node.val > result[*stack.last().unwrap()] {
let idx = stack.pop().unwrap();
result[idx] = node.val;
}
stack.push(result.len());
result.push(node.val);
current = &node.next;
}
for idx in stack {
result[idx] = 0;
}
result
}
}