Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1517
Question Name: Kth Node from End
Question Description: Give an single-linked list, find the Kth last node from the end. If there are less than K nodes in the list, you should return null.
Input: the input might contain multiple test cases. Inside each test case, the first line is two intergers N and K (1 <= N, K <= 1000). N means the size of the list. K means the node to find. The second line includes N integers, as the value of each node in the list.
Output: the value of the node if exist, or “NULL” otherwise.
1 2 3 4 5 6 7 8 | Input: 5 2 1 2 3 4 5 1 0 5 Output: 4 NULL |
Be careful to the corner case.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | /** * Filename : KthNodeFromEnd.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-08-07 * JDK used : 1.7 * Changelog : None */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class KthNodeFromEnd { /** * Definition for singly-linked list and its operation. */ static private class ListNode { public Object val; public ListNode next; /** * The constructor of ListNode * @param x: an object to be the value of this ListNode. */ public ListNode(Object x) { val = x; next = null; } /** * Treat the current node as the head node, find and return * the Kth last node. * @param k : find the Kth last node. * @return the node if exist, or null otherwise. */ ListNode findKthNodeFromEnd(int k) { // Skip k nodes. ListNode former = this; for(int i = 0; i < k; ++i) { // Totally the number of nodes is less than k. if (former == null) return null; former = former.next; } // Find the Kth last node. ListNode latter = this; while (former != null) { latter = latter.next; former = former.next; } return latter; } } /** * Stub for test. * @param args * @throws IOException */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int size, k; ListNode head = null, current = null, result = null; while (st.nextToken() != StreamTokenizer.TT_EOF) { // Start a new test case. size = (int) st.nval; st.nextToken(); k = (int) st.nval; // Get the test array. head = current = result = null; while (size > 0) { st.nextToken(); if (head == null) { current = head = new ListNode((int) st.nval); } else { current.next = new ListNode((int) st.nval); current = current.next; } --size; } // Find the kth last node. result = head.findKthNodeFromEnd(k); System.out.println(result == null ? "NULL" : result.val); } } } |