N'th node from the end of a Linked List

N'th node from the end of a Linked List

N'th node from the end of a Linked List  

Need to find the N'th node from the end of Singly Linked List. Since its singly linked we can't traverse bidirectional and important condition is to traverse only once from start to end of the Linked List. Suppose if the length of Linked List is less than N then return -1.

Solution:
> Use 2 pointers where 1st pointer will be traversing from start to end and 2nd pointer will be starting when 1st pointer reaches N'th node.
> In such a way that when 1st pointer reaches the last node in Linked List 2nd pointer will be placed in the N'th node from last.

Let see simple Java code to implement LinkedList and to find the N'th node from last just by traversing only once.

public class FindLLNode {

 class LinkedList {
  int data;
  LinkedList next;

  public LinkedList(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {

  int val[] = new int[] { 23, 7, 10, 45, 9, 11 };

  int findNode = 3;

  FindLLNode obj = new FindLLNode();

  LinkedList start = obj.createLinkedList(val);

  int nthNodeVal = obj.findLLNode(start, findNode);

  System.out.println("nth Node Value from last : " + nthNodeVal);
 }

 private LinkedList createLinkedList(int[] val) {
  LinkedList start = null, temp = null;
  for (int i : val) {

   LinkedList node = new LinkedList(i);
   if (start == null) {
    start = temp = node;
   } else {
    temp.next = node;
    temp = temp.next;
   }
  }
  return start;
 }

 private int findLLNode(LinkedList start, int findNode) {

  LinkedList p1 = start, p2 = start;
  int i = 0;
  boolean flag = false;
  while (p1 != null) {
   if (i >= findNode) {
    p2 = p2.next;
    flag = true;
   }
   p1 = p1.next;
   i++;
  }
  if (!flag)
   return -1;
  return p2.data;
 }
}

OUTPUT:

3rd Node Value from last : 45

Convert a Binary Tree into its Mirror Tree

Convert a Binary Tree into its Mirror Tree

Mirroring Binary Tree  

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged as given below example.

public class MirroringBinaryTree {

 class NODE {

  int data;
  NODE left;
  NODE right;

  public NODE(int data) {
   this.data = data;
   left = right = null;
  }
 }

 public static void main(String[] args) {

  MirroringBinaryTree obj = new MirroringBinaryTree();

  int val[] = new int[] { 23, 34, 12, 10, 36, 35, 40, 55 };

  NODE root = obj.createBinaryTree(val);

  System.out.print("\n\n INORDER ::::::: ");
  obj.inOrderTraversal(root);

  root = obj.mirror(root);

  System.out.print("\n\n INORDER AFTER MIRROR::::::: ");
  obj.inOrderTraversal(root);
 }

 /*
  * Mirror the binary tree
  */
 public NODE mirror(NODE node) {
  if (node == null)
   return node;

  NODE left = mirror(node.left);
  NODE right = mirror(node.right);

  /* swap left and right pointers */
  node.left = right;
  node.right = left;

  return node;
 }

 /*
  *  BST in-order traversal
  */
 public void inOrderTraversal(NODE root) {

  if (root.left != null) {
   inOrderTraversal(root.left);
  }

  System.out.print(root.data + ", ");

  if (root.right != null) {
   inOrderTraversal(root.right);
  }
 }

 /*
  * Create binary tree by given array
  */
 public NODE createBinaryTree(int val[]) {
  NODE root = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (root == null) {
    root = tmp;
   } else {
    NODE lastNode = getLastNode(root, i);
    if (i > lastNode.data) {
     lastNode.right = tmp;
    } else {
     lastNode.left = tmp;
    }
   }
  }
  return root;
 }

 /*
  * Get parent node the join current node
  */
 public NODE getLastNode(NODE root, int val) {

  if (val > root.data) {

   if (root.right == null) {
    return root;
   } else
    return getLastNode(root.right, val);
  } else {

   if (root.left == null) {
    return root;
   } else
    return getLastNode(root.left, val);
  }
 }
}

OUTPUT:

 INORDER ::::::: 10, 12, 23, 34, 35, 36, 40, 55, 

 INORDER AFTER MIRROR::::::: 55, 40, 36, 35, 34, 23, 12, 10, 

Find the middle node of a given linked list

Find the middle node of a given linked list

traverse the linked list only once to get middle node  

Given a singly linked list, find the middle NODE of the linked list. For example, if given linked list is 1->2->3->4->5 then output should be 3.

If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.

CONDITION:

• Need to traverse the linked list only once. 

public class MiddleNode {

 class NODE {
  
  int data;
  NODE next;

  public NODE(int data) {
   this.data = data;
   this.next = null;
  }
 }
 
 public static void main(String[] args) {

  MiddleNode obj = new MiddleNode();

  int val[] = new int[] { 3, 6, 7, 8, 9, 11, 13, 15, 17, 22, 24, 25, 28};
  
  /* Create linked list */
  NODE start = obj.createLinkedList(val);
  
  /* Get middle NODE */
  NODE middleNode = obj.getMiddleNode(start);
  
  System.out.println("MIDDLE NODE : "+middleNode.data);
 }
 
 /*
  * Create linked base based on given array
  */
 public NODE createLinkedList(int val[]) {
  NODE start = null;
  for (int i : val) {
   NODE tmp = new NODE(i);
   if (start == null) {
    start = tmp;
   } else {
    NODE mover = start;
    while (mover.next != null) {
     mover = mover.next;
    }
    mover.next = tmp;
   }
  }
  return start;
 }
 
 /*
  * Getting middle NODE just by traversing only once
  */
 public NODE getMiddleNode(NODE start) {
  NODE slow = start, fast = start;
  while(fast.next != null && fast.next.next != null) {
   slow = slow.next;
   fast = fast.next.next;
  }
  if(fast.next != null) {
   slow = slow.next;
  }
  return slow;
 }
}

OUTPUT:

MIDDLE NODE : 13

Stack implementation using Linked List

Stack implementation using Linked List

Stack using Linked List  

We have seen Stack implementation using array in our earlier tutorials. Now lets see same stack implementation using Linked List and how to push() and pop() values in Stack. Below is the simple example to push() integers into Stack internally having Linked List nodes with total stack size of 10.

class NODE {
 
 NODE link;
 int data;
 
 public NODE() {
 }
 
 public NODE(int data) {
  this.data = data;
 } 
}

public class StackUsingLinkedList {

 NODE root;
 int stackSize = 0;
 int stackLimit = 10;
 
 public static void main(String[] args) {
  
  StackUsingLinkedList obj = new StackUsingLinkedList();
  
  for(int i =0;i<11;i++){
   obj.push(i+10);
  }
  
  for(int i =0;i<11;i++){
   System.out.println(obj.pop());
  }
 }
 
 private int pop(){
  if(stackSize == 0){
   System.out.println("Stack empty ....");
   return -1;   
  }
  NODE tmp = root;
  root = root.link;
  stackSize--;
  return tmp.data;
  
 }
 
 private void push(int val){
  if(stackLimit == stackSize) {
   System.out.println("Stack Full ....");
   return;
  }
  if(root == null){
   root = new NODE(val);
   root.link = null;   
  }else{
   NODE tmp = new NODE(val);
   tmp.link = root;
   root = tmp;
  }
  System.out.println("PUSH ::: "+stackSize + " :: "+val);
  stackSize++;
 }
}

OUTPUT:

PUSH ::: 0 :: 10
PUSH ::: 1 :: 11
PUSH ::: 2 :: 12
PUSH ::: 3 :: 13
PUSH ::: 4 :: 14
PUSH ::: 5 :: 15
PUSH ::: 6 :: 16
PUSH ::: 7 :: 17
PUSH ::: 8 :: 18
PUSH ::: 9 :: 19
Stack Full ....
19
18
17
16
15
14
13
12
11
10
Stack empty ....
-1