0

this code prints Kth to the last element in the LinkedList using recursion. With LinkedList containing abcdef and k=4.

The expected output is cdef

With recursion, I wanted to use a local Iterator to trace the position of the node, itrLocal in method kToLast(). But, I found that itrLocal was not saved when returned from the recursive call.

Is this a bug ? 

import java.util.Iterator;
import java.util.LinkedList;

//with recursion  O(n) space and O(n) time.
public class KthToLast {

    public KthToLast() {
    }

    public static void main(String[] args){

        LinkedList s = new LinkedList();

        s.add("a");
        s.add("b");
        s.add("c");
        s.add("d");
        s.add("e");
        s.add("f");

        KthToLast k = new KthToLast();
        LinkedList resultList= new LinkedList();
        int n = k.kToLast(s.iterator(), 4, resultList);     
    }//main


    private int kToLast(Iterator<String> itr, int k, LinkedList resultList)    {

        Iterator<String> itrLocal = itr;


        if (!itr.hasNext()) {
           return k;

        }
        else {
            String data = (String) itr.next();

            int n=  kToLast(itr,k, resultList)-1;

            if (n >= 0) {
                resultList.add(data);
            }
            if (n==0){
                Iterator reverse = resultList.descendingIterator();
                while (reverse.hasNext()){
                    System.out.print(reverse.next());
                }//if



            //value of data is reserved for each recursion
            if  (n >= 0) {

            /* why would itrLocal change with itr ? itrLocal at each  
               recursion call was not reserved.   is this a bug ?
             */
              while (itrLocal.hasNext()){
                  System.out.println(itrLocal.next());
              }               
            }//if           
            return n;           
        }//else             
    }//ktolast
}//class
user207421
  • 305,947
  • 44
  • 307
  • 483
Louise
  • 129
  • 3
  • 1
    `Iterator itrLocal = itr;` doesn't make a copy of the iterator. It's the same object, with another name. – Jonathon Reinhart Aug 21 '16 at 21:15
  • does this implementation comply to rule of recursion ? itrLocal is a local variable. – Louise Aug 21 '16 at 21:28
  • 2
    No, it is not a local variable. Having two variables point to the same reference still means: only **one** reference there. Hint: before doing such complex algorithms, learn a bit more about the essentials of Java basics. It looks like you are trying to build a skyscraper; but you dont know how to use a shovel to dig the hole for the basement. – GhostCat Aug 21 '16 at 21:31
  • I see the two Iterators pointed to 1 reference. Are there ways I can refer to – Louise Aug 21 '16 at 23:29
  • Since Iterator is reference, I passed index and LinkedList as parameters and used ListIterator to print the K to Last elements. – Louise Aug 22 '16 at 03:10

0 Answers0