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