题目: 删除链表的倒数第 N 个结点

分析

双指针

在三数之和的问题中，双指针的移动方向是相向而行，而本题中的双指针是同向而行，而且每次都是同时移动，相当于把n个节点作为一个大节点看待，当把这个联合节点右移，当这个节点最右侧部分到达尾部的时候，这个联合节点的头部就位于倒数第n个节点。

时间复杂度$O(n)$

代码如下

public class DoublePointSolution {

    static class LinkNode{
        private Integer value;

        private LinkNode nextNode;

        public LinkNode(Integer value){
            this.value = value;
        }

        public static LinkNode getInstance(Integer[] input){
            LinkNode header = new LinkNode(input[0]);
            LinkNode current = header;
            for(int i = 1; i < input.length; i ++){
                LinkNode next = new LinkNode(input[i]);
                current.nextNode = next;
                current = next;
            }

            return header;
        }

        public Integer getValue() {
            return value;
        }

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

        public LinkNode getNextNode() {
            return nextNode;
        }

        public void setNextNode(LinkNode nextNode) {
            this.nextNode = nextNode;
        }

        public String toString(){
            LinkNode header = this;
            StringBuilder sb = new StringBuilder("");
            while(true){
                sb.append(header.value);
                if((header = header.nextNode) != null){
                    sb.append("->");
                }else{
                    break;
                }
            }

            return sb.toString();
        }
    }

    public static LinkNode removeCountDownNNode(LinkNode header, int n){
        LinkNode slowPoint = header;
        LinkNode fastPoint = header;
        for(int i = 0; i < n; i ++){
            fastPoint = fastPoint.nextNode;
        }

        while(true){
            fastPoint = fastPoint.nextNode;

            if(fastPoint == null){
                LinkNode next = slowPoint.nextNode.nextNode;
                slowPoint.nextNode = next;
                break;
            }else{
                slowPoint = slowPoint.nextNode;
            }
        }

        return header;
    }

    public static void main(String[] args){
        LinkNode linkList = LinkNode.getInstance(new Integer[]{9,8,7,6,5,4,3,2,1});
        System.out.println(linkList);
        linkList = removeCountDownNNode(linkList, 3);
        System.out.println(linkList);
    }

}