1. C# / Говнокод #16482

    +139

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    Есть односвязный список. Каждый элемент списка содержит указатель на следующий элемент (next). 
Нам известен указатель на первый элемент списка (root). Необходимо без использования каких-либо 
дополнительных структур данных и без изменения структуры элементов списка определить зациклен ли данный список.

Ответ

public static boolean isCycleList(Item root){ 
        Item first = root;     
        while(first.getNext() != null){ 
            Item subFirst = root; 
            do { 
                if (subFirst == first.getNext()) 
                    return true; 
                subFirst = subFirst.getNext(); 
            } 
            while (subFirst != first.getNext());         
            first = first.getNext(); 
        } 
        return false; 
    }

    Запостил: kegdan, 05 Августа 2014

    Комментарии (21) RSS

    • ava kegdan 05.08.2014 16:29 # 0

      Из сайтика вопросов собеседования и ответов к ним.
      Ответить

    • ava guest 05.08.2014 17:16 # −1

      > while (subFirst != first.getNext());

      он долбоеб что ли?
      Ответить

      • ava guest 05.08.2014 17:16 # 0

        а, там сверху еще do. подумаешь, гест ошибся. хехе. ладненько.
        Ответить

        • ava inkanus-gray 05.08.2014 17:23 # 0

          Да, синтаксис сишки — говно, потому что цикл с предусловием и цикл с постусловием сходу не отличишь.
          Ответить

    • ava guest 05.08.2014 18:02 # 0 

      static bool isCycled(Item root)
        {
            Item cur = root;
            Item prev = null;
            while (cur != null)
            {
                Item seek = root;
                while (seek != null && seek.next != cur)
                    seek = seek.next;
                if (seek != prev)
                    return true;
                prev = cur;
                cur = cur.next;
            }
            return false;
        }
      Ответить

      • ava kegdan 05.08.2014 18:04 # +2 

        private static bool HasCycle(p p)
    {
        p f = p, s = p;
        while ((s = s.Next) != null && (s = s.Next) != null && (f = f.Next) != s) ;
        return s != null;
    }
        Ответить

    • ava roman-kashitsyn 05.08.2014 18:13 # 0

      Неужели никто не вспомнит избитое решение это избитой задачи? Про два итератора - быстрый и медленный.

      Про это уже даже книги пишут 
      http://www.elementsofprogramming.com/book.html
      Доступная бесплатно глава как раз об этом.
      Ответить

      • ava kegdan 05.08.2014 18:16 # 0

        А чем мое решение не таково?
        Ответить

        • ava roman-kashitsyn 05.08.2014 18:18 # 0

          Да, вроде похоже. Написано только вырвиглазно.
          Ответить

          • ava kegdan 05.08.2014 18:21 # 0

            Да, надо было класс большой буквой назвать. А так - сишное решение, норм
            Ответить

            • ava roman-kashitsyn 05.08.2014 18:26 # +2

              Надо было переменные нормально назвать. fast и slow, например. А у тебя быстрый итератор - s, а медленный - f. Офигенно логично.
              Ответить

            • ava 1024-- 05.08.2014 18:30 # 0

              > сишное решение
              Два изменения одной переменной в одном выражении настораживает сишника и заставляют подсознательно искать УБ.
              Ответить

              • ava kegdan 05.08.2014 18:32 # +1

                Ушлого Байтоеба?
                Ответить

                • ava 1024-- 05.08.2014 18:41 # 0

                  Нет. Два присваивания - как-то медленно. Вот одно присваивание вместо джвух - это да, Ушлый Байтоёб!
                  Ответить

                • ava Abbath 05.08.2014 21:50 # +1

                  Это дрессировщик карманного льва?
                  Ответить

      • ava MAPTOBCKuu_nemyx 26.04.2024 20:26 # 0

        Ну как, не вспомнили?
        Ответить

    Добавить комментарий