Implement an algorithm to find the kth to last element of a singly linked list.

CC150-2.2.java

public class Main {

	/**
	 * 2.2 Implement an algorithm to find the k th
	 * to last element of a singly linked list.
	 * 
	 * we have defined k such that passing in k = 1 would return
	 * the last element,k = 2 would return to the second to last
	 * element,and soon.It is equally acceptable to define k such
	 * that k = 0 would return the last element.
	 * 
	 * @Runtime & spaces
	 * runtime: O(n)
	 * space:   O(1)
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main so = new Main();
		ListNode a = new ListNode(1);
		ListNode b = new ListNode(2);
		ListNode c = new ListNode(3);
		ListNode d = new ListNode(4);
		ListNode e = new ListNode(5);
		ListNode f = new ListNode(6);
		ListNode g = new ListNode(7);
		a.next = b;
		b.next = c;
		c.next = d;
		d.next = e;
		e.next = f;
		f.next = g;
		ListNode result = so.findkthElement(a, 1);
		if (result != null)
			System.out.println(result.val);
		else
			System.out.println("error");
	}

	public ListNode findkthElement(ListNode p, int k) {
		if (k < 0)
			return null;
		if (p == null)
			return p;
		ListNode fast = p;
		for (int i = 0; i < k - 1; i++) {
			fast = fast.next;
			// if the length of the linked list is less than k
			if (fast == null)
				return null;
		}
		ListNode slow=p;
		while (fast.next != null) {
			fast=fast.next;
			slow=slow.next;
		}
		return slow;
	}
}