题解 | #在链表中删除倒数第K个节点#（快慢指针法）

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.List;

class Node {

    private Node next;

    private int value;

    public Node(int value) {
        this.value = value;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public static Node createNodeList(Integer[] values) {
        Node head = new Node((values[0]));
        Node node = head;
        for (int i = 1; i < values.length; i++) {
            Node newNode = new Node(values[i]);
            node.next = newNode;
            node = newNode;
        }
        return head;
    }

    public static Node createNodeList(String[] values) {
        Node head = new Node(Integer.parseInt(values[0]));
        Node node = head;
        for (int i = 1; i < values.length; i++) {
            Node newNode = new Node(Integer.parseInt(values[i]));
            node.next = newNode;
            node = newNode;
        }
        return head;
    }
}

class DeleteBackwardsK {

    //快慢指针法，快指针先走k步
    public static void deleteBackwardsK(Node head, int n, int k) {
        if (n < k||n==1)return;
        StringBuilder sb = new StringBuilder();
        Node n_fast = head;//快指针
        Node n_low = head;//慢指针
        //慢指针的前一位指针（删除一个节点需要找到其前一个节点）
        Node n_forward = new Node(0);
        n_forward.setNext(head);
        //快指针先走k步
        for (int i = 0; i < k; i++) {
            n_fast = n_fast.getNext();
        }
        //快慢指针一起走，到快指针走完为止，慢指针刚好指向目标位置
        while (n_fast != null) {
            n_fast = n_fast.getNext();
            n_low = n_low.getNext();
            n_forward = n_forward.getNext();
        }
        //删除目标位置节点
        n_forward.setNext(n_low.getNext());
        //输出
        n_low = head;
        while (n_low != null) {
            sb.append(n_low.getValue()).append(" ");
            n_low = n_low.getNext();
        }
        System.out.print(sb.toString());
    }

}

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        String[] strings1 = input.readLine().split(" ");
        int length = Integer.parseInt(strings1[0]);
        int k = Integer.parseInt(strings1[1]);
        String[] strings2 = input.readLine().split(" ");
        Node head = Node.createNodeList(strings2);
        DeleteBackwardsK.deleteBackwardsK(head, length, k);
    }

}