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){
        LinkedList.Node t1 = ll.head;
        LinkedList.Node t2 = ll.head;
        
        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){ 
        LinkedList<T> ll = new LinkedList<>();
        for(T t:a){ll.add(t);}
        return ll;
    }
    
    public static void main(String[] args){
        Integer[] array = new Integer[]{0,1,2,3,4,5,6,7};
        LinkedList<Integer> ll = buildList(array);
        System.out.println(nToLast(ll, 2));
    }
}

public class LinkedList <T>{
    
    Node head;
    
    class Node{
        Node next;
        T value;
        
        Node(T value){this.value = value;}
    }
    
    public void add(T value){
        if(head==null){head = new Node(value); return;}
        Node t = head;
        while(t.next!=null){t = t.next;}
        t.next = new Node(value); 
    }
    
    public boolean isEmpty(){
        return head==null;
    }
    
    @Override
    public String toString(){
        StringBuilder bf = new StringBuilder();
        Node t = head;
        while(t!=null){
            bf.append(t.value);
            t = t.next;
        }
        return bf.toString();
    }
}

Output:

6