題目

這題的關(guān)鍵在與兩個(gè)點(diǎn)

1. 一定要設(shè)置一個(gè)啞結(jié)點(diǎn)，防止刪除第一個(gè)元素時(shí)，導(dǎo)致空指針異常
   

2. 刪除鏈表的元素其實(shí)就等價(jià)于找到這個(gè)元素的前一個(gè)元素
   

方法一：節(jié)點(diǎn)加入集合找索引

先將ListNode存到list 然后直接找到要?jiǎng)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)即可（node.next = node.next.next）

  public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode pre = new ListNode(0, head);//創(chuàng)建啞結(jié)點(diǎn)  解決要?jiǎng)h除的元素時(shí)第一個(gè) 空指針異常List<ListNode> list = new ArrayList<>();//將鏈表節(jié)點(diǎn)存到listListNode h = pre;while(h != null){list.add(h);h = h.next;}//找到要?jiǎng)h除的數(shù)的前一個(gè)節(jié)點(diǎn)ListNode node = list.get(list.size()-1-(n-1)-1);node.next = node.next.next;return pre.next;}

方法二：直接計(jì)算長(zhǎng)度,然后找出要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)

       public static ListNode removeNthFromEnd(ListNode head, int n) {//得出鏈表的長(zhǎng)度int length   =  getLength(head);ListNode pre = new ListNode(0, head);//創(chuàng)建啞結(jié)點(diǎn)  解決要?jiǎng)h除的元素時(shí)第一個(gè) 空指針異常//倒數(shù)n個(gè) 為  length - n + 1int l = length - n + 1;ListNode cur = pre;for (int i = 1; i < l ; i++ ) {cur = cur.next;}cur.next = cur.next.next;return pre.next;}//計(jì)算鏈表長(zhǎng)度public static int getLength(ListNode head){int len = 0;while(head !=null){len ++;head = head.next;}return len;}

方法三：棧

依次入棧，直到null 然后要?jiǎng)h除的元素 n = 多少 就彈出對(duì)少元素 彈出的元素就是要?jiǎng)h除的元素 例如找n=1 倒數(shù)第一個(gè) 則直接彈出棧頂元素刪除即可

此時(shí)當(dāng)彈出n個(gè)數(shù)之后 ，此時(shí)棧頂其實(shí)就是要?jiǎng)h除的數(shù)的前一個(gè)數(shù)了，也滿足將刪除鏈表元素轉(zhuǎn)換為找到要?jiǎng)h除元素的前一個(gè)元素

   public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);//啞結(jié)點(diǎn)  刪除第一個(gè)元素空指針異常Deque<ListNode> stack = new LinkedList<ListNode>(); //棧ListNode cur = dummy;while (cur != null) {stack.push(cur);cur = cur.next;}for(int i = 0; i<n ; i++){stack.pop();//彈出對(duì)應(yīng)的棧頂元素  最后彈出的元素就是要?jiǎng)h除的元素}//此時(shí)要?jiǎng)h除的前一個(gè)元素時(shí)棧頂元素ListNode pre = stack.peek();pre.next = pre.next.next;return dummy.next;}

方法四：前后雙指針

關(guān)鍵在于指針的設(shè)置，fast起始就比slow快一個(gè)節(jié)點(diǎn)，然后按照n=？ fast往前移動(dòng)？個(gè)位置，然后再slow和fast同步移動(dòng)，直到fast走到null，此時(shí)slow指向的就是要?jiǎng)h除元素的前一個(gè)位置（也就是為什么開(kāi)始就要fast比slow快一個(gè)位置的原因，不然等f(wàn)ast走到null了，結(jié)果slow指向的要?jiǎng)h除的元素，這樣不太好執(zhí)行node.next = node.next.next操作，因?yàn)閯h除鏈表的元素其實(shí)就等價(jià)于找到這個(gè)元素的前一個(gè)元素）

    public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);//啞結(jié)點(diǎn)  防止刪除第一個(gè)元素空指針異常ListNode  fir = head;ListNode  bef = dummy;//先指針領(lǐng)先 bef  n 個(gè)位置for(int i=0;i<n;i++){fir = fir.next;}//當(dāng) fir遍歷到鏈表的末尾時(shí)， bef的下一個(gè)節(jié)點(diǎn)就是我們需要?jiǎng)h除的節(jié)點(diǎn)。while(fir !=null){fir =fir.next;bef = bef.next;}bef.next = bef.next.next;return dummy.next;}