Эта записка была разобрана в течение целой недели. Я надеюсь получить некоторую информацию о письменном тесте и интервью.
Эта статья содержит следующее содержимое связанного списка:
1. Создание и обход отдельных списков связаны
2. Найдите количество узлов в одном связанном списке
3. Найдите узел k-last в одном связанном списке (Меч указывает на предложение, вопрос 15)
4. Найдите промежуточные узлы в одном связанном списке
5. объединить два упорядоченных листа связанных списков, и объединенные связанные списки все еще в порядке [Высокая частота возникновения] (шаг за предложением, вопрос 17)
6. Обращение с одним связанным списком [самая высокая частота возникновения] (шаг за предложением, Вопрос 16)
7. Распечатайте один связанный список от конца до начала (Меч указывает на предложение, вопрос 5)
8. Определите, имеет ли один связанный список кольцо
9. Уберите длину кольца в связанном списке
10. В единственном связанном списке выберите отправную точку кольца (меч, указывающий на предложение, вопрос 56). Этот вопрос должен использовать вопросы 8 и 9 выше.
11. Определите первую точку пересечения пересечения между двумя одно связанными списками (Меч указывает на предложение, вопрос 37)
1. Создание и обход отдельных списков связанных списков:
Общественный класс Linklist {public Node Head; Если узл заголовка пуста, что означает, что связанный список еще не создан. Узел и поместите его в текущий узел позади (Correlate новый узел с помощью связанного списка) current.next = new Node (data); /После завершения этой операции придерживаются узла, указывающие на недавно добавленный узел}} // Метод: пройти связанный список (распечатайте связанный список. Параметры метода указывают на то, что обход начинается с узла узла Public Void Print ( Узел Узел) {if (node == null) {return; {// Примечание. Разрешения двух переменных членов здесь не могут быть признаны, потому что частные разрешения доступны только для этого класса. data = data; );В приведенном выше коде узлом узел здесь используется внутренний класс для его представления (строки 33). Самым большим преимуществом использования внутренних классов является то, что они могут получить доступ к частным операциям друг с другом с внешними классами.
Примечание. Характеристики внутреннего класса доступа: внутренние классы могут напрямую получить доступ к членам внешних классов, включая частные классы;
Чтобы облегчить операции с добавлением и обходом, добавьте ток переменной элемента в класс Linklist, чтобы представить индекс текущего узла (строка 03).
В методе пересечения связанного списка (строка 20) узел параметра означает, что он начинается с узла узла и не обязательно должен пройти от узла головного узла.
2. Найдите количество узлов в одном списке связанных:
Обратите внимание, чтобы проверить, пуст ли связанный список. Сложность времени - O (n). Это относительно просто.
Основной код:
// Метод: Получить длину единого связанного списка public int getLength (head node) {if (head == null) {return 0; длина th ++;3. Найдите узел k-last в одном связанном списке:
3.1 Обычные идеи:
Во-первых, выберите весь связанный список от начала до конца, вычислите размер длины связанного списка и получите длину связанного списка, его легко сделать. Связанный список пуст, k равно 0, k равно 1, k больше, чем количество узлов в связанном списке
) Временная сложность - O (n), а общая идея заключается в следующем:
public int findlastnode (int index) {// Индекс представляет узел индекса до конца .// В первый раз, когда я прошел, я получил длину связанного списка, если (head == null) {return -1; Current = Head; I <Size - index;Что мне делать, если интервьюер не позволит вам пересекать длину связанного списка? Далее.
3.2 Идеи улучшения: (эта идея также используется в других вопросах)
Здесь вам нужно объявить два указателя: то есть два переменных типа узла сначала и второй. Первый и второй отделяется положениями K-1, а затем два узла перемещаются назад в целом, пока второй узел не достигнет последнего узла, положение, указанное первым узлом, является положением k-th до последнего узел. Сложность времени - O (n)
Реализация кода: (первая версия)
Public Node FindlastNode (node Head, int index) {if (node == null) {return null; 0; = Second.next;Реализация кода: (окончательная версия) (бросьте исключение, когда K больше, чем количество узлов в связанном списке)
В приведенном выше коде функция, по -видимому, была реализована, но она недостаточно надежна:
Обратите внимание на ситуацию, когда K равен 0;
Если k больше, чем количество узлов в связанном списке, будет сообщено об исключении с нулевым указателем, поэтому здесь необходимо суждение.
Основной код заключается в следующем:
Public Node FindlastNode (node Head, int k) {if (k == 0 || head == null) {return null; позиция для (int i = 0; i <k - 1; i ++) {System.out.println ("I's Value"+i); Значение K уже больше, чем длину связанного списка // бросить новое NullpointerException («Длина связанного списка меньше, чем" + k); null; Второй узел достигает последнего узла.4. Найдите промежуточные узлы в одном связанном списке:
Точно так же интервьюер не позволяет вам рассчитать длину связанного списка.
Идея:
Как второй раздел выше, два указателя устанавливаются первым и вторым, но здесь два указателя движутся в одно и то же время, второй указатель делает два шага каждый раз, и первый указатель занимает один шаг каждый раз, пока второй указатель не достигнет В последнем узле узл, на который указал первым указателем промежуточный узел. Обратите внимание, что связанный список пуст, а количество узлов связанного списка составляет 1 и 2. Сложность времени - O (n).
Реализация кода:
// Метод: Найдите промежуточный узел связанного списка общедоступного узла Findmidnode (node) {if (head == null) {return null; Второй конец перемещает две цифры, первый узел перемещается на один (Second! = NULL && Second.Next! Чтобы NULL в это время, позиция, указанная первым указателем, является положением сначала промежуточного узла;В приведенном выше коде, когда n - равномерное число, полученный промежуточный узел - N/2 + 1 Узел. Например, когда в связанном списке есть 6 узлов, получается четвертый узел.
5. объедините два заказанные односвященные списки, и объединенные связанные списки все еще в порядке:
Этот вопрос часто исследуется различными компаниями.
Например:
Список 1:
1-> 2-> 3-> 4
Список 2:
2-> 3-> 4-> 5
После слияния:
1-> 2-> 2-> 3-> 3-> 4-> 4-> 5
Идея решения:
Сравните связанный список 1 и связанный список 2 рядом друг с другом.
Это похоже на сортировку слияния. Обратите особое внимание на ситуацию, когда оба связанных списка пусты, и один из них пуст. Требуется только пространство O (1). Временная сложность - O (MAX (LEN1, LEN2))
Реализация кода:
// Два параметра представляют собой узлы заголовка двух связанных списков общедоступного узла Mergelinklist (Node Head1, Node Head2) {if (head1 == null && head2 == null) {// Если оба связанных списка являются пустыми return null; if (head1 == null) {return head2; Список // В начале мы позволили текущему узлу указать на меньшие данные в Head1 и Head2 и получаем узел головки if (head1.data <head2.data) {Head = Head1; Далее; ; // В новом связанном списке следующий узел текущего указателя соответствует меньшим данным current.next; (Head2! = NULL) {// Укажите, что связанный список 1 после прохождения, он пуст.Тест кода:
Public static void main (string [] args) {linklist1 = new Linklist (); (i); );Метод добавления и метод печати, используемый в приведенном выше коде, соответствуют подразделу 1.
Эффект бега:
Примечание: решение рекурсивное в «предложении указания мечами», которое кажется немного трудно понять.
6. Инверсия односменного списка: [самая высокая частота возникновения]
Например, связанный список:
1-> 2-> 3-> 4
После инверсии:
4-> 2-> 2-> 1
Идея:
Итерация через оригинальный связанный список от начала до конца, и каждый узел пересекается, и он удален и размещен на переднем конце нового связанного списка. Обратите внимание, что связанный список пуст и есть только один узел. Сложность времени - O (n)
Метод 1: (прохождение)
// Метод: изменение связанного списка Public Node Reverselist (Node Head) {// Если связанный список пуст или есть только один узел, инверсия не требуется, и главный узел исходного связанного списка непосредственно возвращается к Оригинальный список IF (Head == NULL || Заголовок нового связанного списка после инверсии (Current! = NULL) {Next = Current.Next; Следующий узел тека к узлу заголовка нового связанного спискаВ приведенном выше коде код ядра составляет строки 16 и 17.
Метод 2: (рекурсия)
Этот метод немного сложный, поэтому я сейчас не буду говорить об этом.
7. Распечатайте один связанный список от конца до конца:
Для такого инвертированного порядка мы должны подумать о стеке, сначала и первым. Поэтому этот вопрос либо использует стек сами, либо позволяет системе использовать стек, то есть рекурсивный. Обратите внимание на случай, когда связанный список пуст. Сложность времени - O (n)
ПРИМЕЧАНИЕ. Не думайте о том, чтобы изменить один связанный список, а затем пересекать вывод.
Метод 1: (создайте новый стек самостоятельно)
// Метод: распечатать один связанный список из конечного до конца void Reverseprint (Head Head) {if (head == null) {return; Создать новое стек. // Нажмите стек.Метод 2: (Используйте стек системы: рекурсивный, элегантный и краткий код)
public void -print (node head) {if (head == null) {return;Резюме: Метод 2 основан на реализации рекурсии. Явный стек метода 1 реализован на основе циклов, а код более надежный.
8. Определите, имеет ли один связанный список кольцо:
Здесь также используются два указателя.
Поэтому мы используем два указателя для прохождения: первый указатель занимает один шаг за раз, а второй указатель делает два шага за раз. Сложность времени - O (n).
Метод:
// Метод: Определить, имеет ли один связанный список {First = First.Next; кольцо вернуть правдоподобно;Полный код версии: (включая тестовую часть)
Здесь нам также необходимо добавить перегруженный метод add (узлы узла), который следует использовать при создании одностороннего кругового списка.
Linklist.java: публичный класс Linklist {public node head; ll) { / /если заголовок пуст, это означает, что связанный список еще не создан, затем назначить новый узел узлу заголовка = новый узел (Data); Создайте новый узел, поместите его за текущий узел (коррелируйте новый узел с связанным списком) current.next = new Node (data); ; ; Узлы) {if (node == null) {return; Метод: обнаружить, имеет ли один связанный список общедоступного логического First = First.Next; Список имеет кольцо возврата true; int data; Добавить данные в Linklist для (int i = 0; i <4; i ++) {list.add (i); это петля в связанном списке. Примечание. Структура кольца, полученная в это время, представляет собой структуру рисунка 1 в следующем разделе 8. System.out.println (list.hascycle (list.head));Код, который обнаруживает, имеет ли один связанный список кольцо, является строкой 50.
Строка 88: Мы продолжаем добавлять узел заголовка в связанный список, и в настоящее время один связанный список будет зациклен. Окончательный эффект бега верен.
Если 88 строк кода удалены, в настоящее время единственный связанный список не имеет петли, а эффект выполнения является ложным.
9. Уберите список, связанный с кольцом, длина кольца:
Список ссылок, с которым мы обычно сталкиваемся, является следующим: (Рисунок 1)
Длина кольца на рисунке выше составляет 4.
Но возможно, что следующее также следующее: (Рисунок 2)
В это время длина кольца на рисунке выше составляет 3.
Так как же найти длину кольца?
Идея:
Здесь нам нужно сначала использовать метод Hascycle в разделе 7 выше (метод, чтобы определить, есть ли кольцо в связанном списке). Он возвращает значение для узла, где мы встречаемся. Затем мы можем получить узел, где мы встречаемся.
Метод:
// Метод: Определите, имеет ли один связанный список кольцо. Верный узел - это узел, в котором он встречается с общедоступным узлом (голова узла) {if (head == null) {return null; .next; NULL; Узел параметра представляет собой узел, где он соответствует публичному int getCycleLength (узловой узел) {if (head == null) {return 0; current.next;Полный код версии: (включая тестовую часть)
Общественный класс Linklist {Public Node Head; Узел пуст, это означает, что связанный список еще не был создан, а затем присваивайте новый узел Head Node Head = New Node (Data); Текущий узел (корреляция нового узла с помощью связанного списка) current.next = new Node (data); Текущий узел указывает на вновь добавленный узел}} // перегрузка метода: добавить узел в связанный список public void add (node node) {if (node == null) {return; {Head = Node; из узла узла Public Print (Node Node) {if (node == null) {return; current.next; first = head; Сначала связанный с кольцом возврат; Узел параметра представляет собой узел, где он соответствует публичному int getCycleLength (узловой узел) {if (head == null) {return 0; current.next; частное, потому что разрешения частного доступны только для этого класса. int data; = null; ; Процесс - это структура рисунка 2 в этом разделе Turning = list1.hascycle (list1.head); );Эффект бега:
Если приведенный выше код испытаний строк с 104 до 122 изменен на следующее: (т.е. измените структуру на рисунке 2 на структуру на рисунке 1)
Public static void main (string [] args) {linklist1 = new Linklist (); (List1.head); Примечание. Структура этого кольца, полученная в это время, является структурой рисунка 1 в этом разделе. Node Current = list1.hascycle (list1.head);Результаты запустить:
Если вы удалите 8 -ю строку в приведенном выше коде, то связанный список не имеет циклов, поэтому результат работы составляет 0.
10. В единственном связанном списке начальная точка извлеченного кольца:
Список ссылок, с которым мы обычно сталкиваемся, является следующим: (Рисунок 1)
Начальная точка 1 кольца на картинке выше.
Но возможно, что следующее также следующее: (Рисунок 2)
В это время отправная точка кольца на рисунке выше составляет 2.
Метод 1:
Здесь нам нужно использовать метод снятия длины кольца в разделе 8 выше, чтобы получить длину, и использовать этот метод для получения длины кольца. Получив длину кольца, необходимо использовать две переменные указателя. Встречайте, узамий, когда они встречаются.
Примечание. Чтобы найти отправную точку кольца, нам нужно сначала получить длину кольца, и для того, чтобы получить длину кольца, нам нужно сначала определить, есть ли кольцо. Таким образом, здесь используются три метода.
Реализация кода:
Основной код для метода 1:
// Метод: Получите начальную точку кольца. Длина параметра представляет собой длину кольца общедоступный узел getCyclestart (Head Head, int gyclelength) {if (head == null) {return null; к шагу длины для (int i = 0; i <cyclelength; i ++) {second = second.next; ! = null) {First = first.next; вернуть NULL;Полный код версии: (включая тестовую часть)
Общественный класс Linklist {Public Node Head; Узел пуст, это означает, что связанный список еще не был создан, а затем присваивайте новый узел Head Node Head = New Node (Data); Текущий узел (корреляция нового узла с помощью связанного списка) current.next = new Node (data); Текущий узел указывает на вновь добавленный узел}} // перегрузка метода: добавить узел в связанный список public void add (node node) {if (node == null) {return; {Head = Node; из узла узла Public Print (Node Node) {if (node == null) {return; current.next; first = head; Сначала связанный с кольцом возврат; Узел параметра представляет собой узел, где он соответствует публичному int getCycleLength (узловой узел) {if (head == null) {return 0; current.next; Длина параметра представляет собой длину кольца общедоступный узел getCyclestart (Head Head, int gyclelength) {if (head == null) {return null; к шагу длины для (int i = 0; i <cyclelength; i ++) {second = second.next; ! = null) {First = first.next; return null; int data; = null; ; Время - это структура рисунка 2 в этом разделе Turning = list1.hascycle (list1.head); .out.println («Начальная точка кольца" + list1.getcyclestart (list1.head, длина) .data);11. Определите первую точку пересечения, где пересекаются два односменных списка:
«Красота программирования» P193, 5.3, Интервью Вопрос 37 имеет этот вопрос.
Во время собеседования первая реакция людей при столкновении с этим вопросом: пересекайте каждый узел в первом связанном списке. Если во втором связанном списке есть узел, так же, как у узла в первом связанном списке, это означает, что два связанных списка перекрываются в этом узле. Очевидно, что временная сложность этого метода - O (Len1 * len2).
Метод 1: идея использования стека
Мы можем увидеть два связанных списка с общими узлами и частично перекрывающимися, топологическая форма выглядит как Y, но она не может быть X-образной формой. Как показано на рисунке ниже:
Как показано на рисунке выше, если один связанный список имеет общий узел, то последний узел (узел 7) должен быть таким же, и он начинается с определенного узла в середине (узел 6) и Последующие узлы одинаковы.
Теперь проблема заключается в том, что в одном связанном списке мы можем пройти только в последовательности из начальных узлов и, наконец, достичь конечного узла. Последний хвостовой узел, который достигает, сначала сравнивается. Таким образом, мы можем подумать об использовании характеристик стека для решения этой проблемы: поместите узлы двух связанных списков в два стека, так что конечные узлы двух связанных списков расположены в верхней части двух стеков. Давайте сравним.
Таким образом, нам нужно использовать два вспомогательных стека, сложность пространства - O (LEN1+LEN2), а временная сложность - O (LEN1+LEN2). По сравнению с методом грубой силы в начале, эффективность времени была улучшена, что эквивалентно использованию потребления пространства для эффективности времени.
Итак, есть ли лучший способ? Давайте поговорим об этом дальше.
Метод 2: Определите первый узел, где пересекаются два связанных списка: используйте быстрый и медленный указатель, рекомендуется (более оптимальное решение)
В методе 2 выше причина, по которой мы используем стек, заключается в том, что мы хотим пройти через конечные узлы двух связанных списков одновременно. На самом деле, чтобы решить эту проблему, у нас есть более простой способ: сначала перевернуть два связанных списка, чтобы получить их длину. Во время второго прохождения перейдите к | Len1-Len2 |
这种思路的时间复杂度也是O(len1+len2)，但是我们不再需要辅助栈，因此提高了空间效率。当面试官肯定了我们的最后一种思路的时候，就可以动手写代码了。
核心代码：
//方法：求两个单链表相交的第一个交点public Node getFirstCommonNode(Node head1, Node head2) { if (head1 == null || head == null) { return null; } int length1 = getLength(head1); int length2 = getLength(head2); int lengthDif = 0; //两个链表长度的差值Node longHead; Node shortHead; //找出较长的那个链表if (length1 > length2) { longHead = head1; shortHead = head2; lengthDif = length1 - length2; } else { longHead = head2; shortHead = head1; lengthDif = length2 - length1; } //将较长的那个链表的指针向前走length个距离for (int i = 0; i < lengthDif; i++) { longHead = longHead.next; } //将两个链表的指针同时向前移动while (longHead != null && shortHead != null) { if (longHead == shortHead) { //第一个相同的结点就是相交的第一个结点return longHead; } longHead = longHead.next; shortHead = shortHead.next; } return null; } //方法：获取单链表的长度public int getLength(Node head) { if (head == null) { return 0; } int length = 0; Node current = head; while (current != null) { length++; current = current.next; } return length;以上就是有关java链表的经典面试题目，希望可以帮助大家顺利通过面试。