## Tuesday, December 23, 2014

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

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

Consider a single linked list having elements:

0 1 2 3 4 5 6 7

Find 2nd to last.

Last = 7.
2nd to last  = 6.

Algorithm:

1. Maintain two pointers t1 and t2.
2. Traverse t2 for K-1 positions.
3. Now iterate t1 and t2 until t2 hits (null).
4. t1 at this point it Kth to last.

Source:

```public class Code{
public static <T> T nToLast(LinkedList<T> ll, int n){

for(int i=0;t2!=null && i<n-1;++i){
t2 = t2.next;
}
if(t2==null)return null;

while(t2.next!=null){
t1 = t1.next;
t2 = t2.next;
}
return (T)t1.value;
}

public static <T> LinkedList<T> buildList(T[] a){
return ll;
}

public static void main(String[] args){
Integer[] array = new Integer[]{0,1,2,3,4,5,6,7};
System.out.println(nToLast(ll, 2));
}
}```

```public class LinkedList <T>{

class Node{
Node next;
T value;

Node(T value){this.value = value;}
}

while(t.next!=null){t = t.next;}
t.next = new Node(value);
}

public boolean isEmpty(){
}

@Override
public String toString(){
StringBuilder bf = new StringBuilder();
while(t!=null){
bf.append(t.value);
t = t.next;
}
return bf.toString();
}
}```

Output:

6