一方向チェーンテーブルの最後からk番目のノードを見つけるアルゴリズム


再帰と非再帰の2つの方法があります
アルゴリズム1(非再帰方式):最も簡単な方法は最初から遍歴することである.
アルゴリズム2(再帰方式)は、k番目の要素の値を印刷する.
    public static int nthToLast(LinkedListNode head,int k){
        if(head == null){
            return 0;
        }
        int i=nthToLast(head.next,k)+1;
        if(i==k){
            System.out.println(head.data);
        }
        return i;
    }

アルゴリズム3(反復法):より効率的だが、あまり直感的ではない解法.
LinkedListNode nthToLast2(LinkedListNode head, int k) {
        if (k <= 0) {
            return null;
        }
        LinkedListNode p1 = head;
        LinkedListNode p2 = head;

        //p2    k   
        for(int i=0;i<k-1;i++){
            if(p2.next==null){
                return null;
            }
            p2 = p2.next;
        }

        if(p2==null){
            return null;
        }

        /*          p1 p2, p2       */
        /*p1     k   */
        while(p2.next!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }