描述

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针
例如，
给出的链表为: 1\to 2\to 3\to 4\to 51→2→3→4→5, n= 2n=2.
删除了链表的倒数第 n 个节点之后,链表变为1\to 2\to 3\to 51→2→3 →5.

示例1

输入：
{1,2},2    

返回值：
{2}

思路

这道题是要删除倒数第 N 个节点，首先大家要明确一般在链表中是如何删除一个节点的，删除的方法是：找到被删除节点的前置节点，然后将前置节点的 next 指针指向该节点的后置节点。写成代码大概如下：

  node 为当前节点；prev 为 node 的前置节点  
  prev.next = node.next 
  或者这么写 
  prev.next = prev.next.next

咱们这道题使用 “双指针” 的方式来删除那个节点。
首先，定义一个哑节点，就是在头节点之前new一个节点，这个哑节点的作用是为了避免处理头节点一个复杂的情况。
然后，定义两个快慢指针，快指针先走 n 步（n 是删除的倒数第几个），然后快慢指针一起往前走，知道快指针为空。

AC 代码

  public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        if (head == null) {
            return head;
        }
        // 创建哑节点
        ListNode dum = new ListNode(0);
        dum.next = head;
        // 慢指针
        ListNode slow = dum;
        // 快指针
        ListNode fast = head;
        // 往前走 N 步
        for (int i = 0; i < n;i ++) {
            fast = fast.next;
        }
        // 当 fast 不为空时，slow 与 fast 一起走
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 删除节点
        slow.next = slow.next.next;
        return dum.next;
    }

时间复杂度：O(N)，N 为链表长度
空间复杂度：O(1)，没有使用额外空间

最后

这道题其实还有其他的解法，但是这种解法目前看时比较优秀的。大家有兴趣也可以尝试下其他解法。
大家可以去 【牛客网-题库-在线编程】去练习一下。
可以去微信搜索：【蘑菇睡不着】交个朋友～
也可以扫描下方二维码。