题目描述

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

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

---

分析

这一题可以用两种方法来做

• 两次遍历算法
• 一次遍历算法（待补充）

两次遍历算法

思路

我们首先需要知道链表的长度L（链表的元素个数count)，然后这个问题就转换为删除链表中第L-n+1个节点。第一次遍历，我们计算出链表的长度；第二次遍历，我们设置一个指针，将它移动到待删除指针的前一个位置，再执行删除操作。

有一个关键点就是我们要新建一个辅助指针，放在链表头head的前面，这是为了防止一种特殊情况：被删除的元素恰好就是第0个元素（即head）。

源码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode assistant = new ListNode(0);//新建一个辅助指针
        assistant.next = head;
        
        ListNode counter = head; // 计算链表的长度
        int count = 0;
        while (counter != null)
        {
            counter = counter.next;
            count++;
        }
        
        count -= n;//第二次遍历，将指针移动到相应位置
        ListNode current = assistant;
        while (count > 0)
        {
            count--;
            current = current.next;
        }
        
        current.next = current.next.next;//删除操作
        
        return assistant.next;  //此处不是return head;
                                //原因是，head节点可能就是被删除的那个节点，
                                //为了避免这种情况，将返回指针设为assistant.next
    }
}

一次遍历算法

思路

两次遍历算法中，我们只用到了一个指针。在一次遍历算法中，我们要用到两个指针。同时也需要和刚才一样，设置一个辅助指针。

两个指针的初始位置在辅助指针处（即head的前面一个），first指针先出发，让它走n+1步，然后让second指针出发，这样，两个指针之间保持固定的距离n+1，一起移动，直到first指针抵达链表尾部。此时second指针就处于待删除元素的前一个元素，我们就可以将它的next指针指向它的下下个节点。

双指针示意图

源码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode assistant = new ListNode(0);
        assistant.next = head;
        ListNode first = assistant;
        ListNode second = assistant;
        for (int i = 0; i < n + 1; i++)
        {
            first = first.next;
        }
        
        while (first != null)
        {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return assistant.next;
    }
}