跳到文档正文
数据结构 / 链表
09 / 18
我们的可视化工具通过直观的图形界面为链表操作注入生命力。每个节点都表示为一个包含节点值的矩形，箭头显示节点之间的连接。这种顺序可视化使得一眼就能理解链表结构和操作。
我们工具的一个关键特性是动态节点跟踪。当您的代码遍历链表时，无论是在插入、删除还是搜索操作期间，该工具都会突出显示当前节点及其连接。这种视觉反馈对于学习链表操作概念或调试链表相关算法特别有用。
让我们看看一些常见的链表算法及其可视化：
function insertAtHead(head, val) {
const newNode = new ListNode(val);
newNode.next = head;
return newNode;
}
function insertAtTail(head, val) {
const newNode = new ListNode(val);
if (!head) return newNode;
let current = head;
while (current.next) {
current = current.next;
}
current.next = newNode;
return head;
}
function insertAtPosition(head, val, position) {
if (position === 0) return insertAtHead(head, val);
const newNode = new ListNode(val);
let current = head;
let count = 0;
while (current && count < position - 1) {
current = current.next;
count++;
}
if (current) {
newNode.next = current.next;
current.next = newNode;
}
return head;
}
// 使用示例：
let list = new ListNode(1);
list = insertAtTail(list, 2);
list = insertAtPosition(list, 3, 1);
function deleteHead(head) {
if (!head) return null;
return head.next;
}
function deleteTail(head) {
if (!head || !head.next) return null;
let current = head;
while (current.next.next) {
current = current.next;
}
current.next = null;
return head;
}
function deleteAtPosition(head, position) {
if (!head) return null;
if (position === 0) return head.next;
let current = head;
let count = 0;
while (current && count < position - 1) {
current = current.next;
count++;
}
if (current && current.next) {
current.next = current.next.next;
}
return head;
}
// 使用示例：
let list = new ListNode(1);
list.next = new ListNode(2);
list.next.next = new ListNode(3);
list = deleteAtPosition(list, 1);
function reverseList(head) {
let prev = null;
let current = head;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
// 使用示例：
let list = new ListNode(1);
list.next = new ListNode(2);
list.next.next = new ListNode(3);
list = reverseList(list);
function mergeSortedLists(l1, l2) {
const dummy = new ListNode(0);
let current = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 || l2;
return dummy.next;
}
// 使用示例：
let list1 = new ListNode(1);
list1.next = new ListNode(3);
let list2 = new ListNode(2);
list2.next = new ListNode(4);
let merged = mergeSortedLists(list1, list2);
function detectCycle(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;
}
// 使用示例：
let list = new ListNode(1);
list.next = new ListNode(2);
list.next.next = new ListNode(3);
list.next.next.next = list.next; // 创建一个环
detectCycle(list); // true
function findMiddleNode(head) {
if (!head || !head.next) return head;
let slow = head;
let fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 使用示例：
let list = new ListNode(1);
list.next = new ListNode(2);
list.next.next = new ListNode(3);
findMiddleNode(list); // 返回值为2的节点
// @ignore-function-tree
function reverseList(head) {
let prev = null;
let current = head;
while (current) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}
function isPalindrome(head) {
if (!head || !head.next) return true;
// 找到中点
let slow = head;
let fast = head;
while (fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
// 反转后半部分
let secondHalf = reverseList(slow.next);
// 比较前半部分和后半部分
let firstHalf = head;
while (secondHalf) {
if (firstHalf.val !== secondHalf.val) {
return false;
}
firstHalf = firstHalf.next;
secondHalf = secondHalf.next;
}
return true;
}
// 使用示例：
let list = new ListNode(1);
list.next = new ListNode(2);
list.next.next = new ListNode(2);
list.next.next.next = new ListNode(1);
isPalindrome(list); // true
function removeNthFromEnd(head, n) {
const dummy = new ListNode(0);
dummy.next = head;
let first = dummy;
let second = dummy;
// 将第一个指针前进 n+1 步
for (let i = 0; i <= n; i++) {
first = first.next;
}
// 移动两个指针直到第一个指针到达末尾
while (first) {
first = first.next;
second = second.next;
}
// 移除第 n 个节点
second.next = second.next.next;
return dummy.next;
}
// 使用示例：
let list = new ListNode(1);
list.next = new ListNode(2);
list.next.next = new ListNode(3);
list = removeNthFromEnd(list, 2); // 移除值为2的节点