一、C语言实现
1. 先获取链表长度，再从正向遍历
/**
* 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;
}
2. 双指针法，只须要遍历一次
/**
* 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;
}
二、JS实现
1. 先获取链表长度，再从正向遍历
/**
* 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
}
2. 双指针法，只须要遍历一次
/**
* 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
}
三、算法工夫及空间复杂度
1. 链表长度法的工夫及空间复杂度
- 工夫复杂度：O(L)，其中L是链表的长度。
- 空间复杂度：O(1)。
2. 双指针法
- 工夫复杂度：O(L)，其中L是链表的长度。
- 空间复杂度：O(1)。
发表回复