Хочется рассказать о решении классической задачи на списки. Многие знают что такое список и даже с чем его едят, но почему-то затем их забывают. Иногда же полезно вникнуть в суть и порешать задачи, решение которых может и не придти сразу в голову :)
Итак, дан список, нам необходимо определить содержит ли он петлю. Самый простой и действенный способ - воспользоваться так называемым методом бегунка.По списку бежит два бегунка - быстрый и медленный, пусть первый делает два шага за такт, а второй один. Допустим, что нам также известна длина списка = k. Число же шагов до петли пусть будет = l. Тогда если быстрый бегунок на l - k шагов отстает от медленного, а быстрый нагоняет его за 1 шаг в единицу времени, то они встретятся на l - k шагов. В этой самой точке они будут стоять как раз в k шагов от начала петли. Т.е. когда указатели встретятся, нам нужно передвинуть медленный бегунок на голову, а быстрый оставить на месте, при движении их с теми же скоростями место их следующей встречи и будет началом петли :)
Вот такой вот простой алгоритмик :) Как всегда исходник(Java): Исходник
Итак, дан список, нам необходимо определить содержит ли он петлю. Самый простой и действенный способ - воспользоваться так называемым методом бегунка.По списку бежит два бегунка - быстрый и медленный, пусть первый делает два шага за такт, а второй один. Допустим, что нам также известна длина списка = k. Число же шагов до петли пусть будет = l. Тогда если быстрый бегунок на l - k шагов отстает от медленного, а быстрый нагоняет его за 1 шаг в единицу времени, то они встретятся на l - k шагов. В этой самой точке они будут стоять как раз в k шагов от начала петли. Т.е. когда указатели встретятся, нам нужно передвинуть медленный бегунок на голову, а быстрый оставить на месте, при движении их с теми же скоростями место их следующей встречи и будет началом петли :)
Вот такой вот простой алгоритмик :) Как всегда исходник(Java): Исходник
Комментариев нет:
Отправить комментарий