Labels

algorithms (22) Design Patterns (20) java (19) linux (14) Snippet (13) service mix (6) soa (4)

Loop In Linked List

Imagine a tortoise which goes around a circular ground and two hares which run in the same ground faster than the tortoise at some point the hare will reach the tortoise.

That means there is a loop in the linked list.

Here is the sample code.

    public static void main(String[] args) {
Node aNode = new Node(1);
makeLoopedLi(aNode);
System.out.println(hasLoop(aNode));
}

private static boolean hasLoop(Node aNode) {
Node torto = aNode;
Node slowHare = torto.next;
Node fastHare = slowHare.next;
while (torto != null && slowHare != null && fastHare != null) {
if ((torto.a == slowHare.a) || (torto.a == fastHare.a)) {
return true;
}
torto = torto.next;
slowHare = fastHare.next;
fastHare = slowHare.next;
}
return false;
}

private static void makeLoopedLi(Node aNode1) {
Node aNode2 = new Node(2);
Node aNode3 = new Node(3);
Node aNode4 = new Node(4);
Node aNode5 = new Node(5);
Node aNode6 = new Node(6);
Node aNode7 = new Node(7);
aNode1.next = aNode2;
aNode2.next = aNode3;
aNode3.next = aNode4;
aNode4.next = aNode5;
aNode5.next = aNode6;
aNode6.next = aNode7;
aNode7.next = aNode2;
}

}

No comments:

Post a Comment

Search 24 Bytes