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

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
        //方法一，通过链表长度，遍历链表，找到要删除的节点，时间大概需要：90ms
        //特殊值处理，链表为空，返回空指针
//        if(head == null){
//            return null;
//        }
//        ListNode head0 = head;
//        int size = 0;  //计数器
//        while (head0 != null){//统计链表的长度
//            size++;
//            head0 = head0.next;
//        }
//        //特殊值处理，n为链表的长度，即删除第一个节点，返回原链表的第二个节点指针
//        if(size == n){
//            return head.next;
//        }
//        head0 = head;
//        size--;
//        //遍历链表，找到要删除的倒数第n个节点的前驱节点
//        while (size > n ){
//            head0 = head0.next;
//            size--;
//        }
//        //删除倒数第n个节点
//        if(n == 1){//如果n=1,即删除链表的最后一个节点
//            head0.next = null;
//        }else {//如果n!=1,即删除链表的倒数第n个节点
//            head0.next = head0.next.next;
//        }
//        return head;  //返回原链表的头指针

        //方法二：利用快慢指针的特性,时间大概需要：90ms
        //特殊值处理，链表为空，返回空指针
        if(head == null){
            return null;
        }
        ListNode fast = head;  //初始化快指针
        int nn = n;
        while (n > 0){  //快指针先移动n步
            if(fast != null){
                fast = fast.next;
            }
            n--;
        }
        //经过移动n步，此时如果快指针指向空指针，则说明要删除链表的第一个节点，返回链表的第二个节点
        if(fast == null){
            return head.next;
        }
        ListNode flow = head;  //初始化慢指针
        //快慢指针移动，直到快指针指向链表的最后一个节点，此时慢指针指向要删除的节点的前驱节点
        while (fast.next != null){
            fast = fast.next;
            flow = flow.next;
        }
        if(nn == 1){//如果nn=1,即删除链表的最后一个节点
            flow.next = null;
        }else {//如果n!=1,即删除链表的倒数第n个节点
            flow.next = flow.next.next;
        }
        return head;  //返回原链表的头指针
    }
}