Tuesday 21 July 2015

Nth node from end in linked list

1. Maintain two pointers – reference pointer and main pointer.

2. Initialize both reference and main pointers to head. First move reference pointer to n nodes from head.

3. Now move both pointers one by one until reference pointer reaches end.

4. Now main pointer will point to nth node from the end.
    Return main pointer.

Implementation according to list in C

/** implementation according to list in C.**/
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;

public class NthNodeFromLast {
       public static void main(String[] args) {
              List<String> list = new LinkedList<String>();
              list.add("19"); list.add("18");
              list.add("17"); list.add("16");
              list.add("15"); list.add("14");
              list.add("13"); list.add("12");
              list.add("11"); list.add("10");
              list.add("9"); list.add("8");
              list.add("7"); list.add("6");
              list.add("5"); list.add("4");
              list.add("3"); list.add("2");
              list.add("1");
             
              /** find nth index. */
              int n = 5; int count = 0; String ele = null;
              ListIterator<String> itr = list.listIterator();
              ListIterator<String> itr1 = list.listIterator();

              while(itr.hasNext()) {
                     itr.next();
                     count ++;
                     if(count<n) {
                           continue;
                     } else {
                           if(itr1.hasNext()) {
                                  ele = itr1.next();
                           }
                     }
              }
              System.out.println(ele);
       }
}

Implementation according predefined Java collection

/** implementation according predefined java collection.**/
import java.util.LinkedList;
import java.util.List;
public class NthNodeFromLast {

       public static void main(String[] args) {
              List<String> list = new LinkedList<String>();
             
              list.add("19"); list.add("18");
              list.add("17"); list.add("16");
              list.add("15"); list.add("14");
              list.add("13"); list.add("12");
              list.add("11"); list.add("10");
              list.add("9"); list.add("8");
              list.add("7"); list.add("6");
              list.add("5"); list.add("4");
              list.add("3"); list.add("2");
              list.add("1");
             
              /** find nth index. */
              int n = 5;
              /**
               * java LinkedList implementation maintain the size
               * (keep update while insertion/deletion).
               * So there no extra loop to get the size.
               * */
              int size = list.size();
              int idxStart = size - n;
              System.out.println(list.get(idxStart));
       }
}

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...