Java program having functions to print middle element of linked list(using slow and fast pointers) and printing nth element from last of linked list.
/** * @author vikky.agrawal * Link List print middle element | print nth element from last */ public class LinkedList { Node node = null; public static void main(String[] args) { LinkedList list = new LinkedList(); list.operations(); } public void operations() { this.node = new Node(10); for (int i = 1; i < 6; i++) { add(node, (int) (Math.random() * 100)); } System.out.println("Middle in case of even no of elements:"); printMiddle(node); add(node, 65); System.out.println("Middle in case of odd no of elements:"); printMiddle(node); printNthFromLast(node, 5); } //Print Nth element from last for given value of N public void printNthFromLast(Node root, int n) { int i = n; if (root == null) { return; } if (i > size(root)) { System.out.println("Not enough elements"); return; } Node node = root; Node nodeback = root; while ((node.getLink() != null) && (--i > 0)) { node = node.getLink(); } if (node.getLink() != null) { while (node.getLink() != null) { nodeback = nodeback.getLink(); node = node.getLink(); } } System.out.println("N = " + n + " element from last is :" + nodeback.getData()); } /** * Print middle element using slow and fast pointers. */ public void printMiddle(Node root) { if (root == null) { return; } System.out.println("Linked list is "); print(root); Node hare = null; Node tortoise = null; boolean temp = false; if (size(root) % 2 == 0) temp = true; if (temp) { hare = root.getLink(); tortoise = root; } else { hare = root; tortoise = root; } while (hare != null && hare.getLink() != null) { hare = hare.getLink().getLink(); tortoise = tortoise.getLink(); } if (temp) { System.out.println("Middle elements :" + tortoise.getData() + " and " + tortoise.getLink().getData()); } else { System.out.println("Middle element is :" + tortoise.getData()); } } /** * Helper functions for LinkedList */ public void add(Node ptr, int data) { if (ptr == null) { System.out.println("Always null ?"); ptr = new Node(data); } else { Node newptr = ptr; while (newptr.getLink() != null) { newptr = newptr.getLink(); } newptr.setLink(new Node(data)); newptr.getLink().setLink(null); } } public void print(Node ptr) { if (ptr == null) { return; } Node ptr1 = ptr; System.out.print(ptr1.getData() + "->"); while ((ptr1 = ptr1.getLink()) != null) { System.out.print(ptr1.getData() + "->"); } System.out.println("/n"); } public int size(Node ptr) { if (ptr == null) { return -1; } Node ptr1 = ptr; int i = 1; while ((ptr1 = ptr1.getLink()) != null) { i++; } return i; } /** * static inner class for LinkedList Data Structure */ private static class Node{ private int data; private Node link; Node(){ } Node(int data){ //mergedList=new Node(); this.setData(data); this.setLink(null); } public int getData(){ return this.data; } public Node getLink(){ return this.link; } public void setData(int data){ this.data=data; } public void setLink(Node link){ this.link=link; } } }
No comments:
Post a Comment