题解 | #删除链表的倒数第n个节点#快慢指针/栈/递归

解法1:快慢指针

先找到倒数第n+1个节点，然后删除倒数第n个节点

如果这个节点是头节点，需要特殊处理一下

import java.util.*;
public class Solution {
    public ListNode removeNthFromEnd (ListNode head, int n) {
        if (head == null || head.next == null) {
            return null;
        }
        int count = 1;
        // find the node before Nth node
        ListNode prev  = FindLastKthNode(head, n + 1);
        // remove nTh node
        // if Nth is the first node, remove head
        if(prev == null){
            head = head.next;
            return head;
        }
        ListNode nThNode = prev.next;
        prev.next = nThNode.next;
        nThNode.next = null;
        return head;
    }

    public ListNode FindLastKthNode (ListNode head, int k) {

        if (head == null || k == 0) {
            return null;
        }
        if (head.next == null && k == 1) {
            return head;
        }
        if (head.next == null && k > 1) {
            return null;
        }

        int count = 1;
        ListNode slow = head;
        ListNode fast = head;
        while (count < k && fast.next != null) {
            fast = fast.next;
            count++;
        }
        if (count < k) {
            return null;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

解法2:使用栈

也是先找到倒数第N+1个节点先

import java.util.*;

public class Solution {

    public ListNode removeNthFromEnd (ListNode head, int n) {
        if (head == null || head.next == null) {
            return null;
        }
        Stack<ListNode> visited = new Stack<ListNode>();
        ListNode current = head;
        while(current != null){
            visited.push(current);
            current = current.next;
        }
        int count = 0;
        ListNode prevOfN = null;
        while(!visited.empty() && count < n+1) {
            prevOfN = visited.pop();  
            count++;          
        }
        if(count < n+1){
            prevOfN = null;
        }
        if(prevOfN == null) {
            return head.next;
        }
        ListNode nNode = prevOfN.next;
        prevOfN.next = nNode.next;
        nNode.next = null;
        return head;
    }
}

解法3:递归

import java.util.*;
public class Solution {
    int size = 0;
    public ListNode removeNthFromEnd (ListNode head, int n) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode prevOfNthNodeFromEnd = FindKthNodeFromEnd(head, n + 1);
        if (prevOfNthNodeFromEnd == null) {
            return head.next;
        }
        ListNode nThNodeFromEnd = prevOfNthNodeFromEnd.next;
        prevOfNthNodeFromEnd.next = nThNodeFromEnd.next;
        nThNodeFromEnd.next = null;
        return head;
    }

    public ListNode FindKthNodeFromEnd (ListNode head, int k) {

        if (head == null) {
            return null;
        }
        ListNode node = FindKthNodeFromEnd(head.next, k);
        size++;
        if (size < k) {
            return null;
        } else if (size == k) {
            return head;
        } else {
            return node;
        }
    }
}