CareerCup

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.

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");
}

}

Hi if there are odd number of nodes I guess it will go into infinite loop?

public class CircularLinkedList {
    private Node head;
    public Node getMiddle() {
        if(head == null) return null;

        Node slow = head;
        Node fast = head;
        while(fast.next()!=head && fast.next().next()!=head) {
            fast = fast.next().next();
            slow = slow.next();
        }

        return slow;
    }
}

void display_middle(struct node **h)
{
struct node *p1 = *h, *p2 = *h;

while (p2 && p2->next) {
p1 = p1->next;
p2 = p2->next->next;
if (p2 == *h || p2->next == *h)
break;
}
printf("%d\n",p1->data);
}