#
Find Kth from Tail

/*************************************************************************** * Author: Isai Damier * Title: Singly Linked List * Project: geekviewpoint * Package: datastructure * * Description: A LinkedList is a data structure that allows access * to a collection of data using pointers/references. While an * array can also be defined as above, LinkedLists and arrays differ * in how they are stored in memory and in the operations they * allow. Unlike an array that must be stored in a block of memory, * the nodes of a LinkedList can be stored anywhere because each * node has a reference to the node that succeeds it. Because the * nodes are stored so loosely, inserting nodes into a LinkedList * is easy; whereas in an array, all the succeeding elements must * be shifted. Of course, insertion also means changing the size of * the array, which means creating the entire array anew. * * Perhaps the greatest beauty of LinkedList is that it allows * accessing an entire sequence of nodes using only one variable: * a reference to the first node in the sequence. * * Countless operations can be performed on LinkedLists. Following * are a few, ranging from the common to the very interesting. **************************************************************************/ public class SinglyLinkedList { Node head = null; Node tail = null; /***************************************************************** * Statement: * Retrieve the node that is k units from the tail. * * Time Complexity of Solution: * Best = O(1); Worst = O(n). * * Technical Details: The imagery is to get a poll, k units long. * Place the poll along the LinkedList so that one end * (labeled X) of the poll is by the head node and one end * (labeled Y) is by some other node called tmp. Now slide the * poll along the LinkedList, until the end labeled Y reaches * the tail. At this point, return the node by X. *****************************************************************/ public Node findKthFromTail(int k) { if (0 > k) { return null; } //count k units from the head. Node tmp = head; int count = 0; while (count < k && null != tmp) { tmp = tmp.next; count++; } //if the LinkedList does not contain k elements, return null if (count < k || null == tmp) { return null; } //keeping tab on the kth element from tmp, slide tmp until //tmp equals tail. Then return the kth element. Node kth = head; while (null != tmp.next) { tmp = tmp.next; kth = kth.next; } return kth; } }

public class SinglyLinkedListTest { /** * Test of findKthFromTail method, of class SinglyLinkedList. */ @Test public void testFindKthFromTail() { System.out.println("findKthFromTail"); int[] input = {9, 4, 5, 2, 1, 12, 6, 7, 4, 8, 3, 0, 16, 19, 11}; SinglyLinkedList linkedList = new SinglyLinkedList(); for (int i = 0; i < input.length; i++) { linkedList.addToTail(input[i]); } int k = 0; int last = input.length - 1; assertEquals(input[last - k], linkedList.findKthFromTail(k).data); k = last / 2; assertEquals(input[last - k], linkedList.findKthFromTail(k).data); k = last; assertEquals(input[last - k], linkedList.findKthFromTail(k).data); k = last + 21; assertEquals(null, linkedList.findKthFromTail(k)); k = -1; assertEquals(null, linkedList.findKthFromTail(k)); } }