今日leetCode 19.删除链表的倒数第N个结点

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 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

进阶：你能尝试使用一趟扫描实现吗？

题解：

方法：双指针法

利用两个指针，给两个指针设置N + 1的间距，那么当快的哪个指针指到最后一个节点的下一个节点(即null)时，慢指针会指到删除目标的前一个位置

图解

 

代码演示：

/*** 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 dumyNode = new ListNode(0);dumyNode.next = head;ListNode fastIndex = dumyNode;ListNode slowIndex = dumyNode;for(int i = 0; i < n + 1;i++) {fastIndex = fastIndex.next;}while(fastIndex != null){slowIndex = slowIndex.next;fastIndex = fastIndex.next;}slowIndex.next = slowIndex.next.next;return dumyNode.next;}
}