怎么做网页二维码_深圳公司排名名字_软文世界官网_重庆森林为什么叫这个名字

题目来源

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

题目解析

本题可以使用 “双指针” 来解题。

定义一个快指针 fast，一个慢指针 slow，初始时都指向 head；

然后，让 fast 指针先走 n 步；

之后，让 slow、fast 指针同时走，直到 fast == null，此时 slow 指针指向的就是链表的倒数第 n 个节点。

fast 先走 n 步，然后 slow、fast 才同时走，则 slow 和 fast 将会一直保持 n 步的差距，那么当 fast 越界时（即 fast == null 时），slow 就处于倒数第 n 个节点。

比如示例1：

但是本题的链表是单向链表，即当前节点只能通过next找到下一个节点，而无法找到上一个。

因此，我们想要删除倒数第 n 个节点，则需要找到倒数第 n+1 个节点，按照前面slow、fast指针逻辑，则当fast走到倒数第1个节点时，slow位于倒数第n+1个节点位置

以示例1为例：

找到倒数第 n+1 个节点后，删除倒数第 n 个节点的操作为：

slow.next = slow.next.next

当链表为单节点链表时，上面slow、fast指针运动会存在问题，比如示例2：

为了避免上面问题，我们可以为输入链表，添加一个虚拟头节点 dummy_head

C源码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {struct ListNode* dummy_head = (struct ListNode*)malloc(sizeof(struct ListNode)); // 定义一个虚拟头节点（更好处理单节点链表）dummy_head->val = 0;dummy_head->next = head;struct ListNode* fast = dummy_head;struct ListNode* slow = dummy_head;for (int i = 0; i < n; i++) { // 先让 fast 指针走 n 步，目的是为了让 fast 和 slow 之间差 n 步fast = fast->next;}while (fast->next != NULL) { // 然后 fast、slow 指针同时走，当fast走到倒数第 1 个节点时，slow 此时处于倒数第 n + 1 个节点，因为 fast 和 slow 之间差 n 步fast = fast->next;slow = slow->next;}slow->next = slow->next->next; // 删除倒数第n个节点，其中slow是倒数第n+1个节点return dummy_head->next;
}

C++源码实现

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummy_head = new ListNode(0, head); // 定义一个虚拟头节点（更好处理单节点链表）ListNode* fast = dummy_head;ListNode* slow = dummy_head;for (int i = 0; i < n; i++) { // 先让 fast 指针走 n 步，目的是为了让 fast 和 slow 之间差 n 步fast = fast->next;}while (fast->next != nullptr) { // 然后 fast、slow 指针同时走，当fast走到倒数第 1 个节点时，slow 此时处于倒数第 n + 1 个节点，因为 fast 和 slow 之间差 n 步fast = fast->next;slow = slow->next;}slow->next = slow->next->next; // 删除倒数第n个节点，其中slow是倒数第n+1个节点return dummy_head->next;}
};

Java源码实现

/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy_head = new ListNode(0, head); // 定义一个虚拟头节点（更好处理单节点链表）ListNode fast = dummy_head;ListNode slow = dummy_head;for (int i = 0; i < n; i++) { // 先让 fast 指针走 n 步，目的是为了让 fast 和 slow 之间差 n 步fast = fast.next;}while (fast.next != null) { // 然后 fast、slow 指针同时走，当fast走到倒数第 1 个节点时，slow 此时处于倒数第 n + 1 个节点，因为 fast 和 slow 之间差 n 步fast = fast.next;slow = slow.next;}slow.next = slow.next.next; // 删除倒数第n个节点，其中slow是倒数第n+1个节点return dummy_head.next;}
}

Python源码实现

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def removeNthFromEnd(self, head, n):""":type head: Optional[ListNode]:type n: int:rtype: Optional[ListNode]"""dummy_head = ListNode(0, head)fast = dummy_headslow = dummy_headfor i in range(n):fast = fast.nextwhile fast.next:fast = fast.nextslow = slow.nextslow.next = slow.next.nextreturn dummy_head.next

JavaScript源码实现


// Definition for singly-linked list.
// function ListNode(val, next) {
//   this.val = (val === undefined ? 0 : val)
//   this.next = (next === undefined ? null : next)
// }// function toList(nums) {
//   const head = new ListNode(nums[0]);//   let node = head;
//   for (let i = 1; i < nums.length; i++) {
//     node.next = new ListNode(nums[i]);
//     node = node.next;
//   }//   return head;
// }/*** @param {ListNode} head* @param {number} n* @return {ListNode}*/
var removeNthFromEnd = function (head, n) {const dummy_head = new ListNode(0, head); // 定义一个虚拟头节点（更好处理单节点链表）let fast = dummy_head;let slow = dummy_head;for (let i = 0; i < n; i++) { // 先让 fast 指针走 n 步，目的是为了让 fast 和 slow 之间差 n 步fast = fast.next;}while (fast.next != null) { // 然后 fast、slow 指针同时走，当fast走到倒数第 1 个节点时，slow 此时处于倒数第 n + 1 个节点，因为 fast 和 slow 之间差 n 步fast = fast.next;slow = slow.next;}slow.next = slow.next.next; // 删除倒数第n个节点，其中slow是倒数第n+1个节点return dummy_head.next;
};// removeNthFromEnd(toList([1]), 1);