#CC150 #CC150-chap2 2.2 Implement an algorithm to find the kth to last element of a singly linked list.

FindKthToLast.java

package chap2;

/**
 * 2.2 Implement an algorithm to find the kth to last element of a singly linked
 * list. *
 * 
 * We define 1st to the last as the last node.
 * 
 * @author xl16
 * 
 */
public class FindKthToLast {

	/**
	 * Solution 1: Iterate through the list first to get its length, then
	 * iterate through it again to get the element at the index len-k. Or we can
	 * ask if the length is known then we don't need to do the first step.
	 * 
	 * 
	 * Time: O(n)
	 * 
	 * Space: O(1)
	 * 
	 * @param head
	 * @param k
	 * @return
	 */
	public static Node findKthToLastByFindingLen(Node head, int k) {
		if (head == null || k <= 0) {
			return null;
		}
		// Use another object to reference the input node to get length
		Node pointer = head;
		int len = 0;
		// Iterate through the list to find length
		while (pointer != null) {
			len += 1;
			pointer = pointer.next;
		}
		// The k cannot be larger than the length
		if (k > len) {
			return null;
		}
		// Iterate through the list and return the elemenet with index n-k
		int i = 0;// index
		while (i < len - k) {
			head = head.next;
			i++;
		}
		return head;
	}

	/**
	 * Solution2: Use the runner technique. Use two pointers, move the runner k
	 * steps ahead of the current pointer (if the runner reaches null it means k
	 * is larger than the length, return null), then move them together one step
	 * at a time. When the runner reaches the end the current points to the
	 * len-k th element.
	 * 
	 * Time: O(n)
	 * 
	 * Space: O(1)
	 * 
	 * @param head
	 * @param k
	 * @return
	 */
	public static Node findKthToLastByRunner(Node head, int k) {
		if (head == null || k <= 0) {
			return null;
		}
		// Use a ruuner that is k steps ahead of the current pointer. Then the
		// runner and the current pointer move together, when the runner reaches
		// the end the current pointer is at the n-kth element or null
		Node runner = head;
		Node current = head;
		int i = 0;
		while (i < k) {
			if (runner == null) {
				return null;
			}
			runner = runner.next;
			i++;
		}
		// Two pointers move together
		while (runner != null) {
			runner = runner.next;
			current = current.next;
		}
		return current;
	}

	/**
	 * Solution in the book, uses recursion to keep track of a counter, when it
	 * reaches the end of the list, set it to 0. Each parent call adds 1 to the
	 * counter, when the counter equals k, we have reached the kth to the last
	 * element of the list. But this solution cannot return the element, can
	 * only print it.
	 * 
	 * Time: O(n)
	 * 
	 * Space: O(n) because of recursion
	 * 
	 * @param head
	 * @param k
	 * @return
	 */
	public static int printKthToLastByRecursion(Node head, int k) {
		if (head == null) {
			return 0;
		}
		int i = printKthToLastByRecursion(head.next, k);
		if (i == k) {
			System.out.println(head.data);
		}
		return i;
	}

	/**
	 * Solution in the book, create a wrapper class of the counter, we can mimic
	 * passing by reference
	 * 
	 * Time: O(n)
	 * 
	 * Space: O(n) because of recursion
	 * 
	 * @param head
	 * @param k
	 * @param i
	 * @return
	 */
	public static Node kthToLastByRecursionWithWrapper(Node head, int k,
			IntWrapper i) {
		if (head == null) {
			return null;
		}
		Node node = kthToLastByRecursionWithWrapper(head.next, k, i);
		i.value += 1;
		if (i.value == k) {
			return head;
		}
		return node;
	}

	public static class IntWrapper {
		public int value = 0;
	}

	public static void main(String args[]) {
		FindKthToLast.Node n = new Node(0);
		n.appendToTail(1);
		// n.appendToTail(2);
		// n.appendToTail(3);
		int k = 1;

		System.out.println("Original                 : " + n.toString());
		Node result = findKthToLastByRunner(n, k);
		if (result != null) {
			System.out.println(k + "th to the last element  : "
					+ result.toString());
		} else {
			System.out.println("Result is null");
		}

	}

	/**
	 * Implementation of a simple LinkedList
	 * 
	 * @author xl16
	 * 
	 */
	static class Node {
		Node next = null;
		int data;

		public Node(int d) {
			data = d;
		}

		public void appendToTail(int d) {
			Node end = new Node(d);
			Node n = this;
			while (n.next != null) {
				n = n.next;
			}
			n.next = end;
		}

		public String toString() {
			Node n = this;
			String str = "";
			while (n.next != null) {
				str += String.valueOf(n.data) + "->";
				n = n.next;
			}
			// The last node
			str += String.valueOf(n.data) + "->null";
			return str;
		}
	}
}