Накануне выпускного года в Школе компьютерных наук,
Сяо Хуэй, который искал работу, наткнулся на Ревеня, ученого из того же отдела...
Во время разговора Сяо Хуэй вспомнил ситуацию, когда он ходил на собеседование на прошлой неделе...
Существует односвязный список, и в связанном списке могут быть «кольца», как показано на рисунке ниже. Как с помощью программы определить, является ли связанный список циклическим связным списком?
метод первый:Во-первых, начиная с головного узла, пройдите по очереди каждый узел односвязного списка. Каждый раз, когда проходится новый узел, все узлы перед новым узлом пересматриваются от головного узла, и новый идентификатор узла сравнивается со всеми идентификаторами узлов перед этим узлом по очереди. Если обнаруживается, что один и тот же идентификатор узла существует во всех узлах перед новым узлом, это означает, что узел был пройден дважды, а связанный список имеет кольцо; если такой же узел не существует во всех предыдущих узлах, продолжайте обход следующего нового узла и продолжайте повторять операцию только что.
Например, такой связный список: A->B->C->D->B->C->D, при переходе к узлу D нам нужно сравнить предыдущие узлы A, B, C и есть нет такого же узла. В это время следующим новым узлом, который нужно пройти, является B, и B существует в узлах A, B, C и D перед B, поэтому B появляется дважды, и считается, что связанный список имеет цикл.
Предположим, что расстояние от головного узла связанного списка до точки входа равно D, а длина кольца связанного списка равна S. Тогда временная сложность алгоритма равна 0+1+2+3+....+(D+S-1) = (D+S-1)*(D+S)/2, что можно просто понять как О (N*N). Однако этот алгоритм не создает дополнительного места для хранения, и сложность пространства можно просто понять как O (1).
Способ второй:Сначала создайте коллекцию HashSet с идентификатором узла в качестве ключа для хранения пройденных узлов. Затем, начиная с головного узла, пройти по очереди каждый узел односвязного списка. Каждый раз, когда проходится новый узел, новый узел сравнивается с узлом, хранящимся в коллекции HashSet. Если в HashSet обнаружен тот же идентификатор узла, это означает, что связанный список имеет кольцо. Если тот же идентификатор узла не существуют в HashSet, новый идентификатор узла сохраняется в HashSet, а затем входит в следующий узел и продолжает повторять операцию только что.
Этот метод по процессу аналогичен способу 1, существенное отличие состоит в том, что HashSet используется в качестве дополнительного кеша.
Предположим, что расстояние от головного узла связанного списка до точки входа равно D, а длина кольца связанного списка равна S. Каждый раз, когда сложность поиска элементов Hashset Element - это O (1), так что общая сложность времени составляет 1 * (d + s) = d + s, можно просто понимать как O (n). И космическая сложность алгоритма или D + S - 1, может быть просто понята как O (n).
Ожидание уведомления не уведомлено, это признанный язык на рабочем месте.
Это воспоминание о трагедии Сяо Хуэя...
Способ третий:Сначала создайте два указателя 1 и 2 (две ссылки на объект в java), которые указывают на головной узел связанного списка. Затем запустите большой цикл в теле цикла, позвольте указателю 1 перемещаться вниз по одному узлу за раз, позвольте указателю 2 перемещаться вниз по двум узлам за раз, а затем сравните, совпадают ли узлы, на которые указывают два указателя. Если они совпадают, считается, что связанный список имеет цикл, а если отличается, продолжается следующий цикл.
Например, в связанном списке A->B->C->D->B->C->D оба указателя изначально указывают на узел A и входят в первый раунд цикла, указатель 1 перемещается на узел B, и указатель 2 перемещается на C. Во втором цикле указатель 1 перемещается в узел C, а указатель 2 перемещается в узел B. В третьем цикле указатель 1 перемещается на узел D, а указатель 2 перемещается на узел D. В это время два указателя указывают на один и тот же узел, и определяется, что связанный список имеет кольцо.
Этот метод можно описать и на более ярком примере: на круговой дорожке два бегуна стартуют в одном месте, один спортсмен быстрый, а другой медленный. Когда двое бегут какое-то время, более быстрый спортсмен неизбежно будет догонять и снова догонять более медленного спортсмена просто потому, что дорожка круговая.
Предположим, что расстояние от головного узла связанного списка до точки входа равно D, а длина кольца связанного списка равна S. Тогда цикл будет выполняться S раз (почему именно S раз, заинтересованные студенты могут догадаться сами), что можно просто понимать как O(N). Помимо двух указателей, дополнительное хранилище не используется, поэтому сложность пространства составляет O (1).
Вопрос один:Определить, пересекаются ли два односвязных списка, и если да, то найти пересечение.
Вопрос второй:В циклическом связанном списке, как найти точку входа связанного списка?