2.2.java

/* 
【解题思路】
1.使用static variable存count, 然后recursive调用函数。

【时间复杂度】
1.O(n)

【空间复杂度】
1.O(n)

【gist link】	Java
https://gist.github.com/LinyinWu/1013d20adbcd1ac39cbd
【test case】
"FOLLOWuuP" k=4	--->	"W"
*/

public class Solution {
	static int count = 0;
	final static int k = 4;
	
	public static Node kthToLast(Node n) {
		if(n == null)
			return null;
		Node next = kthToLast(n.next);
		count++;
		if(count == k) 
			return n;
		return next;
	}
	public static void main(String[] args) {
		Node n = new Node('F');
		n.next = new Node('O');
		n.next.next = new Node('L');
		n.next.next.next = new Node('L');
		n.next.next.next.next = new Node('O');
		Node c = n.next.next.next.next;
		c.next = new Node('W');
		c.next.next = new Node('u');
		c.next.next.next = new Node('u');
		c.next.next.next.next = new Node('P');
		printList(n);
		System.out.println("\nafter:");
		Node k = kthToLast(n);
		if(k != null)
			System.out.println(k.val);
		else
			System.out.println("null");
		
	}
	
	public static void printList(Node n) {
		for(Node run = n;run != null;run=run.next) {
			System.out.print(run.val);
		}
	}
    
}

class Node {
	char val;
	Node next;
	Node(char in) {
		val = in;
		next = null;
	}
}