3
\$\begingroup\$

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

Any comments or feedback regarding this?

I came up with another algorithm that uses HashMap to find the kth to the last element in a LinkedList.

public static int getKthToLastElement(LinkedListNode head, int k){
    LinkedListNode n = head;

    if(head == null || k < 0)
        return -1;

    int index = 0;
    HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
    while (n != null){
        map.put(index,n.data);
        index++;
        n = n.next;
    }

    if(k > map.size() -1){
        return  -1;
    }
    return map.get(map.size() - 1 - k);
}
\$\endgroup\$
  • \$\begingroup\$ You could do this without using any extra data structures via recursion. You should try it as an exercise. :) \$\endgroup\$ – Mike Borkland Sep 4 '18 at 14:51
  • \$\begingroup\$ Sure thing @MikeBorkland. I am just trying to figure out multiple solutions to a given problem :) Thanks for the exercise :) \$\endgroup\$ – Samsruti Dash Sep 4 '18 at 14:59
1
\$\begingroup\$

Your if(head == null || k < 0) special case is unnecessary, since it is covered by the if(k > map.size() -1) test. You should also never omit the "optional" braces for a multi-line block.

Actually, the if(k > map.size() -1) test could also be eliminated, if you used Map.getOrDefault(…, -1).

The loop would be more easily recognized if written as a for loop.

public static int getKthToLastElement(LinkedListNode head, int k) {
    int index = 0;
    Map<> map = new HashMap<Integer, Integer>();
    for (LinkedListNode n = head; n != null; n = n.next) {
        map.put(index++, n.data);
    }
    return map.getOrDefault(map.size() - 1 - k, -1);
}

I think that converting the linked list to an ArrayList would be better than converting it to a HashMap. You would then be converting a cumbersome linked list into a kind of list that is useful and idiomatic in Java.

\$\endgroup\$
1
\$\begingroup\$

Always use curly braces, even when they’re not required by the compiler.

It’s a poor practice for LinkedListNode to expose its internals directly (n.data, n.next. Use accessors.

Use interfaces where appropriate (Map<Integer, Integer> map = new HashMap<>()). You don’t need any HashMap-specific behavior after declaration.

Use whitespace consistently and idiomatically. There should be a space before a {, between if and (, and after a ,.

Your algorithm uses more space than you need to. This problem can be solved in O(n) time with O(1) space. Keep a leading pointer and a trailing pointer, with the leading pointer k steps ahead. When the leading pointer hits the end, the trailing pointer points to the desired node.

If you were to apply all my suggestions, your code might look more like:

public static int getKthToLastElement(final LinkedListNode head, final int k) {
    if ((head == null) || (k < 0)) {
        return -1;
    }

    LinkedListNode leadingPointer = head;
    for (int i = 0; i < k; i++) {
        leadingPointer = leadingPointer.getNext();
        if (leadingPointer == null) {
            return -1;
        }
    }

    LinkedListNode trailingPointer = head; 
    while (leadingPointer.hasNext()) {
        leadingPointer = leadingPointer.getNext();
        trailingPointer = trailingPointer.getNext();
    }

    return trailingPointer.getData();
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback. I will surely follow your tips for write good code :) \$\endgroup\$ – Samsruti Dash Sep 6 '18 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.