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

题目

中文题目
英文题目

分析 : (斜体是被推翻或者舍弃的 , 黑体是斜体的替代办法)

• 一次遍历 , 我们可以使用双指针 , 快指针与慢指针相差 n 个节点 , 当快指针到达末尾时 , 慢指针就指向需要删除的节点的前一个节点 , 进行删除即可
• 写代码时发现快指针(即前指针)先走(n+1)次更好 , 比如链表有两个元素 , 删除倒数第二个节点时快节点其实最多只能走一次
• 若要删除头结点 , 就必须建立一个辅助节点 , 快指针先走(n+1)次

正确代码 :

/*
 * @lc app=leetcode.cn id=19 lang=java
 *
 * [19] 删除链表的倒数第N个节点
 */

// @lc code=start

// //Definition for singly-linked list.
// class ListNode {
//      int val;
//      ListNode next;
//      ListNode(int x) { val = x; }
// }

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode secondaryNode = new ListNode(-1);
        secondaryNode.next = head;  //创建辅助节点
        ListNode fasNode = secondaryNode;
        ListNode sloNode = secondaryNode;   //快慢节点
        for (int i = 0; i < (n+1); i++) {   //快节点先走
            fasNode = fasNode.next;
        }
        while(fasNode != null){ //两指针等距遍历
            fasNode = fasNode.next;
            sloNode = sloNode.next;
        }
        sloNode.next = sloNode.next.next;   //删除

        return secondaryNode.next;
    }
}
// @lc code=end

问题 :

占用空间较大