一、题目
1、算法题目
“删除给定链表的第n个节点，并返回链表的头结点。”
题目链接：
来源：力扣（LeetCode）
链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个链表，删除链表的倒数第 n **个结点，并且返回链表的头结点。
进阶： 你能尝试使用一趟扫描实现吗？
网络异常，图片无法展示
|
示例 1： 输入： head = [1,2,3,4,5], n = 2 输出： [1,2,3,5] 复制代码
示例 2： 输入： head = [1], n = 1 输出： [] 复制代码
二、解题
1、思路分析
这道题，如果我们要删除节点y，我们需要知道节点y的前节点x，并将x的指针指向y的后节点，但是，因为头结点没有前节点，所以在删除头结点的时候需要进行处理。
可以在头结点前设置一个哑结点(dummy node)，这样头结点的前节点就是哑结点了。
2、代码实现
链表没有头节点，那么弄一个头节点这个问题就简化掉了，然后让一个快指针先走n步，代码参考：
public class Solution { public ListNode RemoveNthFromEnd(ListNode head, int n) { ListNode preHead = new ListNode(); preHead.next = head; ListNode pre, end; pre = preHead; end = preHead; for (var i = 0; i < n; i++) { end = end.next; } while (end.next != null) { pre = pre.next; end = end.next; } // Remove pre.next = pre.next.next; return preHead.next; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(L)
其中L是链表的长度。
空间复杂度： O(1)
三、总结
比较简便的方法就是从头节点开始遍历，得到链表长度L。
随后遍历到第L-n+1个节点的时候，就是我们需要删除的节点。
