一、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)。