119 lines
3.2 KiB
JavaScript
119 lines
3.2 KiB
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
|
||
* @param {number} n
|
||
* @return {ListNode}
|
||
*/
|
||
const removeNthFromEnd = function (head, n) {
|
||
|
||
};
|
||
|
||
function ListNode(val, next) {
|
||
this.val = (val === undefined ? 0 : val);
|
||
this.next = (next === undefined ? null : next);
|
||
}
|
||
|
||
/*
|
||
思路：首先统计列表的长度，根据长度信息找到倒数第n个节点的前一个节点,把它删掉即可
|
||
*/
|
||
function f1(head, n) {
|
||
// 1.获取列表的长度
|
||
const len = getListLength(head);
|
||
// 2.创建哑节点，减少处理逻辑
|
||
const dummyHead = new ListNode(-1);
|
||
dummyHead.next = head;
|
||
// 3.找到要删除节点的前一个节点
|
||
let pre = dummyHead;
|
||
for (let i = 0; i < len - n; i++) {
|
||
pre = pre.next;
|
||
}
|
||
// 4. 删除这个节点
|
||
pre.next = pre.next.next;
|
||
return dummyHead.next;
|
||
}
|
||
|
||
/**
|
||
* 获取链表的节点个数
|
||
* @param {ListNode} head - 链表的头节点
|
||
* @return {number} - 链表的节点个数
|
||
*/
|
||
const getListLength = function (head) {
|
||
let count = 0; // 初始化计数器
|
||
let current = head; // 初始化当前节点为链表头
|
||
|
||
// 遍历整个链表，直到链表末尾
|
||
while (current !== null) {
|
||
count++; // 每遍历一个节点，计数器加一
|
||
current = current.next; // 移动到下一个节点
|
||
}
|
||
|
||
return count; // 返回链表的长度
|
||
};
|
||
|
||
/*
|
||
思路：只需要找到要去除节点的前一个节点就能去掉这个节点，所以核心问题就变成了
|
||
如何寻找这个节点，直接利用快慢指针，首先初始化两个指针在同一位置，然后让快指针
|
||
往后走n步，之后一同走，直到快指针到达最后一个节点，此时的慢指针指向的就是要删除
|
||
节点的前一个节点。
|
||
*/
|
||
|
||
function f2(head, n) {
|
||
const dummyHead = new ListNode(-1); // 建立哑节点，便于处理head
|
||
dummyHead.next = head;
|
||
let slow = dummyHead;
|
||
let fast = dummyHead;
|
||
|
||
// 1.快指针先走n+1步(夺走一部是因为从哑节点开始走)
|
||
for (let i = 0; i <= n; i++) {
|
||
fast = fast.next;
|
||
}
|
||
|
||
// 2.两个指针同时往后走，如果fast已经是最后一个节点，
|
||
while (fast) {
|
||
slow = slow.next;
|
||
fast = fast.next;
|
||
}
|
||
|
||
// 3.删除slow后面的那个节点
|
||
slow.next = slow.next.next;
|
||
|
||
// 4.返回处理后的链表
|
||
return dummyHead.next;
|
||
}
|
||
|
||
/*
|
||
利用栈，f1中我们统计了链表的长度，之后根据长度和n来找到要删除节点的前一个节点，这样实际上遍历
|
||
了两遍，可以直接将所有节点按照顺序压入栈中，之后弹出栈顶的n个元素，剩下的栈顶元素就是我们要操作
|
||
的pre节点
|
||
*/
|
||
|
||
function f3(head, n) {
|
||
const dummyHead = new ListNode(-1); // 建立哑节点，便于处理head
|
||
dummyHead.next = head;
|
||
|
||
// 1.将所有节点压入栈中
|
||
const stack = [];
|
||
let cur = dummyHead;
|
||
while (cur) {
|
||
stack.push(cur);
|
||
cur = cur.next;
|
||
}
|
||
|
||
// 2.弹出栈顶的n个元素
|
||
for (let i = 0; i < n; i++) {
|
||
stack.pop();
|
||
}
|
||
// 3.操作栈顶元素，这个元素就是要删除元素的前一个节点
|
||
const prev = stack[stack.length - 1];
|
||
prev.next = prev.next.next;
|
||
|
||
// 4.返回修改后的链表
|
||
return dummyHead.next;
|
||
}
|