@Test public void testStartOfLoop() { LinkedList<Integer> l = newLinkedList(2, 5, 7); LinkedListNode<Integer> startOfLoop = startOfLoop(l); Assert.assertNull(startOfLoop); LinkedListNode<Integer> runningNode = l.head(); for (; runningNode.successor() != null; runningNode = runningNode.successor()) { if (runningNode.successor().data() == 7) { runningNode.successor().setSuccessor(runningNode); break; } } startOfLoop = startOfLoop(l); Assert.assertNotNull(startOfLoop); Assert.assertEquals(5, startOfLoop.data().intValue()); }
public static LinkedListNode<Integer> startOfLoop(LinkedList<Integer> l) { LinkedListNode<Integer> tortoise = l.head(); LinkedListNode<Integer> hare = l.head(); do { if (tortoise != l.tail()) { tortoise = tortoise.successor(); LOGGER.info("Tortoise was here: {}.", tortoise); } if (hare.successor() != l.tail()) { hare = hare.successor().successor(); LOGGER.info("Hare was here: {}.", hare); } if (tortoise == l.tail() || hare == l.tail()) { LOGGER.info("No loop found."); return null; } } while (!tortoise.equals(hare)); LOGGER.info("Loop found. Tortoise is here: {}, hare is here: {}.", tortoise, hare); for (tortoise = l.head(); !tortoise.equals(hare); tortoise = tortoise.successor(), hare = hare.successor()) ; LOGGER.info("Found start of loop at: {}.", tortoise); return tortoise; }
PracticeQuestionsCh7 { public static LinkedListNode<Integer> startOfLoop(LinkedList<Integer> l) { LinkedListNode<Integer> tortoise = l.head(); LinkedListNode<Integer> hare = l.head(); do { if (tortoise != l.tail()) { tortoise = tortoise.successor(); LOGGER.info("Tortoise was here: {}.", tortoise); } if (hare.successor() != l.tail()) { hare = hare.successor().successor(); LOGGER.info("Hare was here: {}.", hare); } if (tortoise == l.tail() || hare == l.tail()) { LOGGER.info("No loop found."); return null; } } while (!tortoise.equals(hare)); LOGGER.info("Loop found. Tortoise is here: {}, hare is here: {}.", tortoise, hare); for (tortoise = l.head(); !tortoise.equals(hare); tortoise = tortoise.successor(), hare = hare.successor()) ; LOGGER.info("Found start of loop at: {}.", tortoise); return tortoise; } }
PracticeQuestionsCh7 { public static LinkedListNode<Integer> startOfLoop(LinkedList<Integer> l) { LinkedListNode<Integer> tortoise = l.head(); LinkedListNode<Integer> hare = l.head(); do { if (tortoise != l.tail()) { tortoise = tortoise.successor(); LOGGER.info("Tortoise was here: {}.", tortoise); } if (hare.successor() != l.tail()) { hare = hare.successor().successor(); LOGGER.info("Hare was here: {}.", hare); } if (tortoise == l.tail() || hare == l.tail()) { LOGGER.info("No loop found."); return null; } } while (!tortoise.equals(hare)); LOGGER.info("Loop found. Tortoise is here: {}, hare is here: {}.", tortoise, hare); for (tortoise = l.head(); !tortoise.equals(hare); tortoise = tortoise.successor(), hare = hare.successor()) ; LOGGER.info("Found start of loop at: {}.", tortoise); return tortoise; }  }
PracticeQuestionsCh7 { public static LinkedListNode<Integer> startOfLoop(LinkedList<Integer> l) { LinkedListNode<Integer> tortoise = l.head(); LinkedListNode<Integer> hare = l.head(); do { if (tortoise != l.tail()) { tortoise = tortoise.successor(); LOGGER.info("Tortoise was here: {}.", tortoise); } if (hare.successor() != l.tail()) { hare = hare.successor().successor(); LOGGER.info("Hare was here: {}.", hare); } if (tortoise == l.tail() || hare == l.tail()) { LOGGER.info("No loop found."); return null; } } while (!tortoise.equals(hare)); LOGGER.info("Loop found. Tortoise is here: {}, hare is here: {}.", tortoise, hare); for (tortoise = l.head(); !tortoise.equals(hare); tortoise = tortoise.successor(), hare = hare.successor()) ; LOGGER.info("Found start of loop at: {}.", tortoise); return tortoise; }  static LinkedListNode<Integer> mergeLists(LinkedList<Integer> l, LinkedList<Integer> f); static LinkedListNode<Integer> startOfLoop(LinkedList<Integer> l); static LinkedListNode<Integer> intersection(LinkedList<Integer> l1, LinkedList<Integer> l2); static void evenOddMerge(LinkedList<Integer> l); static void reverse(LinkedList<Integer> l); }
PracticeQuestionsCh7 { public static LinkedListNode<Integer> startOfLoop(LinkedList<Integer> l) { LinkedListNode<Integer> tortoise = l.head(); LinkedListNode<Integer> hare = l.head(); do { if (tortoise != l.tail()) { tortoise = tortoise.successor(); LOGGER.info("Tortoise was here: {}.", tortoise); } if (hare.successor() != l.tail()) { hare = hare.successor().successor(); LOGGER.info("Hare was here: {}.", hare); } if (tortoise == l.tail() || hare == l.tail()) { LOGGER.info("No loop found."); return null; } } while (!tortoise.equals(hare)); LOGGER.info("Loop found. Tortoise is here: {}, hare is here: {}.", tortoise, hare); for (tortoise = l.head(); !tortoise.equals(hare); tortoise = tortoise.successor(), hare = hare.successor()) ; LOGGER.info("Found start of loop at: {}.", tortoise); return tortoise; }  static LinkedListNode<Integer> mergeLists(LinkedList<Integer> l, LinkedList<Integer> f); static LinkedListNode<Integer> startOfLoop(LinkedList<Integer> l); static LinkedListNode<Integer> intersection(LinkedList<Integer> l1, LinkedList<Integer> l2); static void evenOddMerge(LinkedList<Integer> l); static void reverse(LinkedList<Integer> l); static final Logger LOGGER; }