Kth to last element of a singly linked list

Question

Find the kth to last element of a singly linked list

Any comments?

import org.junit.Test;

public class Solution {
  // Find kth to last element of a singly linked list
  // Solution proposed: Use a runner that is k steps ahead
  // when runner hits end of linked list, slow on kth to end element

  public Node n3 = new Node(3);
  public Node n2 = new Node(2,n3);
  public Node n1 = new Node(1,n2);
  public Node head = new Node(0,n1);


  public Node findKthToLast(Node head, int k){
    // place the runner k steps ahead
    if (head == null){
      return null;
    }

    Node runner = new Node(head);
    Node slow = new Node(head);

    for (int i = 0; i < k; i++){
      if (runner.getNext() == null){
        return null;
      }
      else{
        runner = runner.getNext();
      }
    }

    while (runner != null){
      runner = runner.getNext();
      slow = slow.getNext();
    }

    return slow;
  }

  @Test
  void test1th(){
    System.out.println(findKthToLast(head, 1).getValue());
  }

  @Test
  void testLargerThanList(){
    System.out.println(findKthToLast(head, 15));    
  }

  @Test
  void testNonDegenerate(){
    System.out.println(findKthToLast(head, 2).getValue());
  }


  public static void main(String[] args) {
    Solution e = new Solution();
    e.test1th();
    e.testLargerThanList();
    e.testNonDegenerate();
  }

}

class Node {
  private int value;

  private Node next;

  public Node(int v) {
    value = v;
  }

  public Node(int v, Node n) {
    value = v;
    next = n;
  }


  public Node(Node n){
    this.value = n.value;
    this.next = n.next;
  }

  public Node getNext(){
    return next;
  }
  public int getValue(){
    return value;
  }
  public void setNext(Node n){
    this.next = n;
  }
}

Answer 1

Your code is neat, and, within the confines of the "Solution", you have solved things well.

The algorithm you use is the right one, it's implemented well, and it's all clear. I like it.

There's only one thing that concerns me. The interface of the Node class:

1. The value of the node should be final (not just private).
2. The Node class itself should be private, and should not be passed in to the findKthToLast method (it should be accessed as the private field it is)
3. the return value of the findKthToLast should be the node's value, not the node itself.

There are all concerns that are about the implementation environment, not just the implementation itself. The Solution concept may be the issue.

So, taking that all in to consideration, your solution, given the constraints, is a good one, but the Solution environment and requirements themselves may be the worst of the problems.

Answer 2

Nice solution. You could make the code a little more robust.

Following are how I would go about this.

• In public Node(Node n) use the getters.

• For both constructors in Node, check if n == null and deal with it.

• Instead of Node runner = new Node(head); do Node runner = head; (just for readability, I had to scroll down to see what the constructor does.)

• Declare head n1 n2 and n3 as final.

• In public Node findKthToLast(Node head, int k) make k final and add if (k < 0) return null; at the top of the method.