/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
// 比拟奢侈的算法
// 先求出链表长度，而后依据长度求出要删除的元素正向的地位
// 最初遍历到该元素前一元素进行删除操作
struct ListNode *removeNthFromEnd(struct ListNode *head, int n)
{
int len = 0;
struct ListNode *origin = head;
// 计算链表的长度
while (head)
{
len++;
head = head -> next;
}
// 将 head 从新指向头结点
head = origin;
// 计算是正向第几个节点
int count = len - n;
// 如果是正向第一个结点，则头结点被删除，只须要间接返回头结点的 next 即可
if (count == 0) {return head -> next;}
// 如果不是正向第一个结点（即结点），则间接遍历到该结点的前一个结点
for (int i = 0; i < count - 1; i++) {head = head -> next;}
// 将该节点删除，而后返回头结点的指针
head -> next = head -> next -> next;
return origin;
}
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
// 双指针法，挪动 first 指针使其到的链表末端，同时挪动 second 指针
// 使其指向最终要删除的节点的前一个节点，此时即可删除节点并返回头结点
// 只需一轮循环即可实现
struct ListNode *removeNthFromEnd(struct ListNode *head, int n)
{
// 创立一个哑结点，并将其指向头结点
struct ListNode dumpy = {0, head};
// 将 first 指针指向 head 头指针
struct ListNode *first = head;
// 将 second 指针指向哑结点，此处 dumpy 是构造体，因而须要取地址
struct ListNode *second = &dumpy;
for (int i = 0; i < n; i++)
{first = first->next;}
while (first)
{
first = first->next;
second = second->next;
}
second->next = second->next->next;
// first second 和 head 都是构造体指针，因而能够应用 -> 拜访成员
// dumpy 是构造体，能够间接用点号拜访
return dumpy.next;
}
/**
* 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) {
const origin = head
if (!head) {return null}
let count = 1
while (head.next) {
count++
head = head.next
}
head = origin
if (count <= n) {return origin.next} else {
// 倒数第 n 个数，就是负数第 count - n + 1 个数，那么，只须要遍历到此数的前一个数，即可
// 前一个数则是第 count - n 个数，从第一个数开始遍历，只需遍历 count - n - 1 次就可达到此数
const index = count - n - 1
for (let i = 0; i < index; i++) {head = head.next}
head.next = head.next.next
}
return origin
}
/**
* 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}
*/
// 双指针法，挪动 first 指针使其到的链表末端，同时挪动 second 指针
// 使其指向最终要删除的节点的前一个节点，此时即可删除节点并返回头结点
// 只需一轮循环即可实现
const removeNthFromEnd = function (head, n) {
// 创立一个哑结点，并将它指向头结点
const dumpy = new ListNode(0, head)
// 将第二个指针指向哑结点，第一个指针指向头结点
let second = dumpy
let first = head
// 将第一个指针往前挪动 n 个地位
for (let i = 0; i < n; i++) {first = first.next}
// 挪动第一个指针直到链表结尾，同时挪动第二个指针
while (first) {
first = first.next
second = second.next
}
// 此时第二个指针指向的是倒数第 n 个节点的前一个节点
// 将倒数第 n 个节点删除即可
second.next = second.next.next
// 返回头结点，应用 head 会出错，为什么呢？因为如果要删除的节点是头结点，那么头结点被删除后，// 哑结点间接指向第二个结点，而 head 还是指向头结点，因而会报错。// 所以此时要么返回 head.next，要么返回 dumpy.next。// 而 head.next 的返回须要判断 second.next 是不是指向头结点
// 而 dumpy.next 则间接应用
return dumpy.next
}
- 工夫复杂度：O(L)，其中 L 是链表的长度。
- 空间复杂度：O(1)。
- 工夫复杂度：O(L)，其中 L 是链表的长度。
- 空间复杂度：O(1)。