Interview Question
Country: United States
A Small Implementation of what " PseudoLife " meant to suggested :
O/P :
1->2->3->4->5->6->7->8->9
5 is the middle node
Code :
/*
you have a circular linked list,
how do you find the middle. You can only go through it once.
-Another question from "Cracking the Code".
*/
class Node {
Node its_childNode;
Node grandChildNode;
Integer val; // this is needed to show the answer of the example.
private static Node ROOT_NODE = null;
public static Node initRootAndChildNode(Integer initRootVal, Integer rootChildNodeVal) {
if (Node.ROOT_NODE == null) {
Node.ROOT_NODE = new Node(initRootVal);
Node.ROOT_NODE.its_childNode = new Node(rootChildNodeVal); // no grandparent of this child i.e. Node.ROOT_NODE.grandChildNode is null;
return Node.ROOT_NODE;
}
throw new RuntimeException("No. You cannot Initilise it Twice");
}
public static Node getRootNode() {
return Node.ROOT_NODE;
}
private Node(int _val) {
val = _val;
}
Node init_its_ChildNode(Integer next_val, Node grandParentNode) {
its_childNode = new Node(next_val);
grandParentNode.grandChildNode = its_childNode;
return this;
}
}
public class FindMidPointOfLinkedList {
public static void main(String[] args) {
initiliseNode();
}
private static void initiliseNode() {
Node myFirstNode = Node.initRootAndChildNode(1,2);
Node grandParentNode = null;
grandParentNode = myFirstNode.its_childNode.init_its_ChildNode(3, myFirstNode); // no grandparent for the first child.
grandParentNode = grandParentNode.its_childNode.init_its_ChildNode(4, grandParentNode);
grandParentNode = grandParentNode.its_childNode.init_its_ChildNode(5, grandParentNode);
grandParentNode = grandParentNode.its_childNode.init_its_ChildNode(6, grandParentNode);
grandParentNode = grandParentNode.its_childNode.init_its_ChildNode(7, grandParentNode);
grandParentNode = grandParentNode.its_childNode.init_its_ChildNode(8, grandParentNode);
grandParentNode = grandParentNode.its_childNode.init_its_ChildNode(9, grandParentNode);
grandParentNode = grandParentNode.its_childNode.init_its_ChildNode(10, grandParentNode);
Node answer = Node.getRootNode();
Node loopingNode = Node.getRootNode();
// racing to the last Node
while (loopingNode.grandChildNode != null) {
answer = answer.its_childNode;
loopingNode = loopingNode.grandChildNode;
}
// just to display all the created node in UI
Node nodeIterator = Node.getRootNode();
while (nodeIterator.its_childNode != null) {
if (nodeIterator.grandChildNode != null) {
System.out.print(nodeIterator.val + "->");
} else {
System.out.print(nodeIterator.val);
}
nodeIterator = nodeIterator.its_childNode;
}
while (loopingNode.grandChildNode != null) {
answer = answer.its_childNode;
loopingNode = loopingNode.grandChildNode;
}
System.out.println("\n"+answer.val + " is the middle node");
}
}
Use 3 pointers - first to point to the head node, second to move at a pace of one node at a time and third to move at a pace of 2 nodes at a time. Keep moving the second and third pointers so when the third pointer becomes equal to the first pointer, we have the middle node pointed by the second pointer.
- Murali Mohan August 17, 2013