1. 问题描述
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
2. 实现思路
2.1 自己的思路
~~（一定要写出来啊喂）~
- 先遍历一遍获取链表长度，再结合虚拟头节点删除
public class Solution
{public ListNode RemoveNthFromEnd(ListNode head, int n){var dummyHead = new ListNode(0, head);var preHead = dummyHead;var temp = dummyHead;int count = 0;while (temp.next != null){count++;temp = temp.next;}for (int i = 0; i < count - n; i++)preHead = preHead.next;preHead.next = preHead.next?.next;return dummyHead.next;}
}
2.2 题解思路
19.删除链表的倒数第N个节点 | 双指针 | 虚拟头节点
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
public class Solution {public ListNode RemoveNthFromEnd(ListNode head, int n) {ListNode dummpHead = new ListNode(0);dummpHead.next = head;var fastNode = dummpHead;var slowNode = dummpHead;while(n-- != 0 && fastNode != null){fastNode = fastNode.next;}while(fastNode.next != null){fastNode = fastNode.next;slowNode = slowNode.next;}slowNode.next = slowNode.next.next;return dummpHead.next;}
}
- 时间复杂度: O(n)
- 空间复杂度: O(1)
2.3 优化（或者敲一遍题解？）
好的也是很经典的双指针啊
public class Solution
{public ListNode RemoveNthFromEnd(ListNode head, int n){var dummyHead = new ListNode(0, head);var fast = dummyHead.next;var slow = dummyHead;while (n-- != 0)fast = fast.next ?? null;while (fast != null){fast = fast.next;slow = slow.next;}slow.next = slow.next?.next;return dummyHead.next;}
}
3. 补充知识と杂谈，总结
不过有一说一，也是第一次花十多分钟解出一个mid难度的题，虽然离最优解还差一些距离
但从写完这篇笔记来看一共花了二十四分钟，嗯嗯以后也继续保持叭~每个题都控制在半个小时以内喵