题目
题目来源leetcode
leetcode地址：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
本地调试代码：
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) { ... } public static void main(String[] args) { ListNode node4 = new ListNode(4, null); ListNode node3 = new ListNode(3, node4); ListNode node2 = new ListNode(2, node3); ListNode node1 = new ListNode(1, node2); ListNode listNode = new Solution().removeNthFromEnd(node1, 4); //遍历 printList(listNode); } private static void printList(ListNode listNode) { if(listNode == null){ return; } System.out.print("["); while(listNode != null){ System.out.print(listNode.val); if(listNode.next != null){ System.out.print(","); } listNode = listNode.next; } System.out.print("]"); } }
NO1：虚拟节点+快慢指针
思路： 虚拟头节点+双指针(快慢指针移动)
定义快慢指针，首先让快指针先移动n步。 之后让慢、快指针同时向后进行一步一步移动，一旦快指针指向为null，就表示已经到底了，此时就可以根据慢指针指向的节点进行下一个节点的删除！
代码：
public ListNode removeNthFromEnd(ListNode head, int n) { //头节点为空与删除索引<0情况直接结束 if(head == null || n<1){ return head; } //节点数>=1 ListNode dummy = new ListNode(0,head); //定义快慢指针 ListNode slow = dummy; ListNode fast = dummy; //先让fast走n步 for (int i = 1; i <= n; i++) { fast = fast.next; if(fast == null){ return dummy.next; //若是中途走的过程为null，则表示无法删除，直接返回 } } //快慢指针一起移动，一旦fast为null说明走到底了 while(fast.next!=null){ slow = slow.next; fast = fast.next; } slow.next = slow.next.next; return dummy.next; }
