In my previous posts we talked about single link list, doubly link list. In this post I am sharing my code solution for few practice question which are also frequently asked in interviews too.
Get Nth node value from end of link list
Given a Linked List and a number n, we need to write a method that returns the value at the nth node from end of the Linked List.
Solution: We maintain two references say First and Second. First we move First
to n nodes from head.After that we move both references one by one until First
reaches end. Now Second will point to nth node from the
end.
Lets see in the code now:
public class LinkListPrograms {
//Refer my link list post for link list implementation details
SLL myList = new SLL();
public static void main(String[] args) {
LinkListPrograms myProg = new LinkListPrograms();
myProg.myList.insert(new Node(11),1);
myProg.myList.insert(new Node(42),2);
myProg.myList.insert(new Node(43),1);
myProg.myList.insert(new Node(44),1);
myProg.myList.insert(new Node(45),2);
myProg.myList.insert(51,1);
myProg.myList.insert(52,2);
myProg.myList.insert(53,1);
myProg.myList.insert(54,1);
myProg.myList.insert(55,2);
myProg.myList.insert(56,4);
myProg.myList.insertAtStart(1);
myProg.myList.insertAtStart(2);
myProg.myList.insertAtStart(3);
myProg.myList.insertAtStart(4);
myProg.myList.insertAtStart(new Node(11));
myProg.myList.insertAtStart(new Node(12));
myProg.myList.insertAtStart(new Node(13));
myProg.myList.insertAtStart(new Node(14));
myProg.myList.printList(myProg.myList.getHead());
System.out.println("Nth element form last is: "+myProg.getNthFromLast(5));
}
public Integer getNthFromLast(int n) {
// Check if list is already Empty
if (myList.isEmpty()) {
System.out.println("List is empty returning null;");
return null;
}
Node firstNode, secondNode;
firstNode = secondNode = myList.getHead();
for (int i = 0; i < n; i++) {
firstNode = firstNode.getNext();
if (firstNode == null) {
System.out.println("invalid number given returning null");
return null;
}
}
while (firstNode != null) {
firstNode = firstNode.getNext();
secondNode = secondNode.getNext();
}
return secondNode.getData();
}
}
If we run the program we will get output like this:
Output
========================================================================
List is: [ 14 13 12 11 4 3 2 1 54 55 53 56 51 52 44 45 43 11 42 ]
Nth element form last is: 44
Print middle node value
We traverse linked list using two pointers. Moving one pointer by one and
other pointer by two. When the fast pointer reaches end slow pointer
will reach middle of the linked list.
public class LinkListPrograms {
//Refer my link list post for link list implementation details
SLL myList = new SLL();
public static void main(String[] args) {
LinkListPrograms myProg = new LinkListPrograms();
myProg.myList.insert(new Node(11),1);
myProg.myList.insert(new Node(42),2);
myProg.myList.insert(new Node(43),1);
myProg.myList.insert(new Node(44),1);
myProg.myList.insert(new Node(45),2);
myProg.myList.insert(51,1);
myProg.myList.insert(52,2);
myProg.myList.insert(53,1);
myProg.myList.insert(54,1);
myProg.myList.insert(55,2);
myProg.myList.insert(56,4);
myProg.myList.insertAtStart(1);
myProg.myList.insertAtStart(2);
myProg.myList.insertAtStart(3);
myProg.myList.insertAtStart(4);
myProg.myList.insertAtStart(new Node(11));
myProg.myList.insertAtStart(new Node(12));
myProg.myList.insertAtStart(new Node(13));
myProg.myList.insertAtStart(new Node(14));
myProg.myList.printList(myProg.myList.getHead());
myProg.printMiddle();
}
/* method to get the middle of the linked list */
public void printMiddle() {
/*
* We will Traverse linked list using two reference namely fastRef and
* slowRef Move one first by one and other by two.When the fast ref
* reaches end slow ref will reach middle of the linked listCheck if
* list is already Empty
*/
if (myList.isEmpty()) {
System.out.println("List is empty");
}
Node fastRef, slowRef;
fastRef = slowRef = myList.getHead();
while (fastRef != null && fastRef.getNext() != null) {
fastRef = fastRef.getNext().getNext();
slowRef = slowRef.getNext();
}
System.out.println("Middle node is: " + slowRef.getData());
}
}
If we run the program we will get output like this:
Output
========================================================================
List is: [ 14 13 12 11 4 3 2 1 54 55 53 56 51 52 44 45 43 11 42 ]
Middle node is: 55
Get number of occurrence of a number in link list
We are require to find how many time a number is present in the list.
Lets see the code now:
public class LinkListPrograms {
//Refer my link list post for link list implementation details
SLL myList = new SLL();
public static void main(String[] args) {
LinkListPrograms myProg = new LinkListPrograms();
myProg.myList.insert(new Node(11),1);
myProg.myList.insert(new Node(42),2);
myProg.myList.insert(new Node(43),1);
myProg.myList.insert(new Node(44),1);
myProg.myList.insert(new Node(45),2);
myProg.myList.insert(51,1);
myProg.myList.insert(52,2);
myProg.myList.insert(53,1);
myProg.myList.insert(54,1);
myProg.myList.insert(55,2);
myProg.myList.insert(56,4);
myProg.myList.insertAtStart(1);
myProg.myList.insertAtStart(2);
myProg.myList.insertAtStart(3);
myProg.myList.insertAtStart(4);
myProg.myList.insertAtStart(new Node(11));
myProg.myList.insertAtStart(new Node(12));
myProg.myList.insertAtStart(new Node(13));
myProg.myList.insertAtStart(new Node(14));
myProg.myList.printList(myProg.myList.getHead());
System.out.println("occurrence is: "+myProg.getOccurrence(11));
}
/*
* Counts the no. of occurrences of a node (search_for) in a linked list
* (head)
*/
Integer getOccurrence(int numTosearchFor) {
// Check if list is already Empty
if (myList.isEmpty()) {
System.out.println("List is empty returning null;");
return null;
}
Node currentNode = myList.getHead();
int count = 0;
while (currentNode != null) {
if (currentNode.getData() == numTosearchFor) {
count++;
}
currentNode = currentNode.getNext();
}
return count;
}
}
If we run the program we will get output like this:
Output
========================================================================
List is: [ 14 13 12 11 4 3 2 1 54 55 53 56 51 52 44 45 43 11 42 ]
occurrence is: 2
Floyd's Cycle-Finding Algorithm
Floyd's cycle-finding algorithm, also called the "tortoise and the hare algorithm" is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.
Traverse linked list using two pointers.
Move one pointer by one and other pointer by two. If these pointers
meet at some node then there is a loop. If pointers do not meet then
linked list doesn’t have loop.
public class LinkListPrograms {
//Refer my link list post for link list implementation details
SLL myList = new SLL();
public static void main(String[] args) {
LinkListPrograms myProg = new LinkListPrograms();
myProg.myList.insert(new Node(11),1);
myProg.myList.insert(new Node(42),2);
myProg.myList.insert(new Node(43),1);
myProg.myList.insert(new Node(44),1);
myProg.myList.insert(new Node(45),2);
myProg.myList.insert(51,1);
myProg.myList.insert(52,2);
myProg.myList.insert(53,1);
myProg.myList.insert(54,1);
myProg.myList.insert(55,2);
myProg.myList.insert(56,4);
myProg.myList.insertAtStart(1);
myProg.myList.insertAtStart(2);
myProg.myList.insertAtStart(3);
myProg.myList.insertAtStart(4);
/*
* Adding two nodes to make a cycle
*/
Node nodeForLoop1 = new Node(22);
Node nodeForLoop2 = new Node(23);
nodeForLoop2.setNext(nodeForLoop1);
myProg.myList.insertAtEnd(nodeForLoop1);
myProg.myList.insertAtEnd(nodeForLoop2);
}
/* Floyd's Cycle-Finding Algorithm */
public boolean detectloop() {
/*
* The fastest way to detect the loop is to use Floyd's Cycle-Finding
* Algorithm Move one pointer by one and other pointer by two. If these
* pointers meet at some node then there is a loop. If pointers do not
* meet then linked list doesn't have loop.
*/
// Check if list is already Empty
if (myList.isEmpty()) {
System.out.println("List is empty returning false:");
return false;
}
Node fastRef, slowRef;
fastRef = slowRef = myList.getHead();
while (fastRef != null && fastRef.getNext() != null) {
fastRef = fastRef.getNext().getNext();
slowRef = slowRef.getNext();
if (slowRef == fastRef) {
//Below method will print node where cycle is present
getLoopStart(slowRef, fastRef);
return true;
}
}
return false;
}
private void getLoopStart(Node slowRef, Node fastRef) {
/*
* Move slowRef to Head. Keep fastRef at Meeting Point. Each are k steps
* /* from the Loop Start. If they move at the same pace, they must *
* meet at Loop Start.
*/
slowRef = myList.getHead();
while (slowRef != fastRef) {
slowRef = slowRef.getNext();
fastRef = fastRef.getNext();
}
// Now n2 points to the start of the loop.
System.out.println("loop at: " + fastRef.getData());
}
}
If we run the program we will get output like this:
Output
============================================================================
loop at: 22
Is loop present: true
Richard Brent's Cycle-Finding Algorithm
In 1980, Brent invented an algorithm that not only worked in linear time, but required less stepping than Floyd's Tortoise and the Hare algorithm (however it is slightly more complex).
Brent's algorithm features a moving rabbit and a stationary, then
teleporting, turtle. Both turtle and rabbit start at the top of the
list. The rabbit takes one step per iteration. If it is then at the same
position as the stationary turtle, there is obviously a loop. If it
reaches the end of the list, there is no loop.
Of course, this by itself will take infinite time if there is
a loop. So every once in a while, we teleport the turtle to the
rabbit's position, and let the rabbit continue moving. We start out
waiting just 2 steps before teleportation, and we double that each time
we move the turtle.
Why move the turtle at all? Well, the loop might not include the
entire list; if a rabbit gets stuck in a loop further down, without the
turtle, it will go forever. Why take twice as long each time?
Eventually, the length of time between teleportations will become longer
than the size of the loop, and the turtle will be there waiting for the
rabbit when it gets back.
Note that like Floyd's Tortoise and Hare algorithm, this one runs in
O(N). However you're doing less stepping than with Floyd's (in fact the
upper bound for steps is the number you would do with Floyd's
algorithm). According to Brent's research, his algorithm is 24-36% faster on average for implicit linked list algorithms.
Lets see the code now:
public class LinkListPrograms {
//Refer my link list post for link list implementation details
SLL myList = new SLL();
public static void main(String[] args) {
LinkListPrograms myProg = new LinkListPrograms();
myProg.myList.insert(new Node(11),1);
myProg.myList.insert(new Node(42),2);
myProg.myList.insert(new Node(43),1);
myProg.myList.insert(new Node(44),1);
myProg.myList.insert(new Node(45),2);
myProg.myList.insert(51,1);
myProg.myList.insert(52,2);
myProg.myList.insert(53,1);
myProg.myList.insert(54,1);
myProg.myList.insert(55,2);
myProg.myList.insert(56,4);
myProg.myList.insertAtStart(1);
myProg.myList.insertAtStart(2);
myProg.myList.insertAtStart(3);
myProg.myList.insertAtStart(4);
myProg.myList.insertAtStart(new Node(11));
myProg.myList.insertAtStart(new Node(12));
myProg.myList.insertAtStart(new Node(13));
myProg.myList.insertAtStart(new Node(14));
myProg.myList.printList(myProg.myList.getHead());
System.out.println(myProg.hasLLoop(myProg.myList.getHead()));
}
/*
* Richard Brent's algo: Richard Brent described an alternative cycle
* detection algorithm,which is pretty much like the hare and the tortoise
* [Floyd’s cycle] except the slow node here doesn't move, but is later
* " teleported" to the position of fast node at fixed intervals
*/
public boolean hasLLoop(Node root) {
if (root == null) {
return false;
}
Node slow = root, fast = root;
int taken = 0, limit = 2;
while (slow.getNext() != null && fast.getNext() != null) {
fast = fast.getNext();
taken++;
if (slow == fast) {
return true;
}
if (taken == limit) {
taken = 0;
limit <<= 1; // equivalent to limit *= 2
slow = fast; // teleporting the turtle to the hare's position
}
}
return false;
}
}
If we run the program we will get output like this:
Output
============================================================================
true
Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.
I will keep adding more Question here :)
No comments :
Post a Comment