题解 | #删除链表的倒数第n个节点#

由于我们需要找到倒数第 n 个节点，因此可以使用两个指针fast 和 slow 同时对链表进行遍历，并且 fast 比 slow 超前 n 个节点。当 fast 遍历到链表的末尾时，slow 就恰好处于倒数第 n 个节点。
具体地，初始时 fast 和 slow 均指向头节点。首先使用 fast 对链表进行遍历，遍历的次数为 n。此时，fast 和 slow 之间间隔了 n-1 个节点，即 fast 比 slow 超前了 n 个节点。
在这之后，同时使用 fast 和 slow 对链表进行遍历。当 fast 遍历到链表的末尾（即 fast 为空指针）时，slow 恰好指向倒数第 n 个节点。

图解：

Python版本

class Solution:
    def removeNthFromEnd(self , head , n ):
        # write code here
        if not head:
            return None
        # 定义快慢指针
        slow = head
        fast = head
        for i in range(n):
            fast = fast.next
        # 判断n是否大于head的长度
        if not fast:
            return head.next
        # 快慢指针同时行走
        while fast.next:
            fast = fast.next
            slow = slow.next
        # 删除结点
        slow.next = slow.next.next
        return head

复杂度分析

时间复杂度O(N)：N表示链表的长度，遍历整个链表

空间复杂度O(1)：双指针占用空间

算法思想二：计算链表长度

解题思路

首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后再从头节点开始对链表进行一次遍历，当遍历到第 L-n+1 个节点时，它就是我们需要删除的节点
为了方便删除操作，可以从哑节点开始遍历 L-n+1 个节点。当遍历到第 L-n+1 个节点时，它的下一个节点就是需要删除的节点，这样只需要修改一次指针，就能完成删除操作

图解：

JAVA版本

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        int length = 0;
        ListNode p = head;
        ListNode q = head;
        // 获取链表的长度
        while(head != null){
            length++;
            head = head.next;
        }
        if(length < 2){
            return null;
        }
        // 特殊情况
        if(n == length){
            return q.next;
        }
        int i = 0;
        while(p != null){
            i++;
            if(i == length - n){
                // 删除结点
                p.next = p.next.next;
            }
            p = p.next;
        }
        return q;
    }
}