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

个人认为这道题不算中等难度，属于简单吧。
三个解题思路：1、双指针；2、HashMap；3、两次遍历
1、双指针
此方法应为本题最佳解法
快指针fast，慢指针slow。fast先行n步，然后fast与slow同时前进，当fast为null，slow指向的节点即为待删除节点。此时引入pre指针指向slow前驱节点。
注意：当出现题目中给出的例子这种情况，即n等于链表长度，删除链表首节点。那么要对pre做判空操作。

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
        ListNode fast=head,slow=head;
        //题目说n保证有效，无需多虑
        for(int i=0;i<n;i++){
            fast=fast.next;
        }
        ListNode pre=null;
        while(fast!=null){
            pre=slow;
            slow=slow.next;
            fast=fast.next;
        }
        if(pre!=null){
            pre.next=slow.next;    
        }else{
            head=slow.next;
        }
        return head;

    }
}

2、HashMap
用HashMap来解决链表问题可以在考虑前驱节点和后继节点方面变的简单，但是性能一般不好，首先空间复杂度肯定会变高。不推荐此种解法。HashMap相当于一个容器，将节点放入其中，然后利用get（）方法找到待删除节点和前驱节点。前驱节点对应len-n，后继节点len-n+2，其中len为链表长度。此方法同样需考虑前驱节点为空的情况

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
        ListNode tn=head;
        HashMap<Integer,ListNode> map=new HashMap<>();
        int i=1;
        while(tn!=null){
            map.put(i++,tn);
            tn=tn.next;
        }
        int len=map.size();
        ListNode tleft=map.get(len-n);
        ListNode tright=map.get(len-n+2);
        if(tleft==null){
            head=tright;
        }else{
            tleft.next=tright;
        }
        return head;
    }
}

3、两次遍历
没实现这种方法，就是第一次遍历获取链表长度，第二次遍历进行删除对应节点。