Отличные программисты, которые не умеют говорить, часто терпят огромные потери на собеседованиях.Вы не можете легко доказать свою силу, говоря. Независимо от того, большая это фабрика или маленькая, большинство интервьюеров не владеют отличными навыками интервьюирования, и они могут лишь наблюдать за поверхностными навыками интервьюеров по нескольким словам. Многие программисты страдают от такой потери, не любят готовиться к собеседованиям, не любят хвастаться фальшивым и несуществующим опытом и способностями и даже не удосуживаются пройти письменный онлайн-тест. вопросы, потому что эти птичьи вопросы вообще не используются в реальной работе.
Но это не то, чем стоит гордиться искренностью, неспособность подготовиться к собеседованию — это неуважение к компании-мишени, а также проявление личного высокомерия. Хотя все интервьюеры надеются, что интервьюер настоящий, а не фальшивый, и не делает поверхностных статей, но когда такой человек действительно стоит перед вами, почти всем интервьюерам это часто не нравится.
Так как же заставить интервьюера смотреть на вас, прилагая как можно меньше поверхностных усилий? Один из методов - показать отличную работу и код реализации личности, но это требует времени и упорного труда.Людей, имеющих возможность делать отличные личные работы, не так много, и большинство из них выматываются в своей загруженной работе. , все время. Другой способ — продемонстрировать свои навыки на этапе письменного тестирования, показать свои отличные способности к программированию на бумаге и заставить интервьюера сразу же почувствовать о вас другое мнение.
Не кричите на вопросы по алгоритму в письменном тесте, вам кажется, что они для гениев программирования. На самом деле, большинство письменных тестовых вопросов компании также исходят из Интернета, которые были испорчены бесчисленным количеством людей. Вы смущены вопросом, а другие нет, это потому, что другие уже задали вопрос, а не из-за IQ.
Возьмем проблему алгоритма, о которой я собираюсь сегодня рассказать — реверсирование односвязного списка, это очень простая задача, но если вы сталкиваетесь с этой проблемой впервые, действительно необходимо написать ее полностью без ошибок. Это заняло много времени. усилий. Ожидается, что этот вопрос может быть легко решен в коротком письменном тестовом разделе, что на самом деле может быть сделано только людьми, очень талантливыми в алгоритмах. Неужели все программисты на большой фабрике гении, в это верят призраки. Гении всегда редки, и большинство из них — посредственности, такие как Лао Цянь.
Хорошо, давайте приступим к делу, начнем с сегодняшней алгоритмической задачи — обращения односвязного списка. Прежде всего, это односторонний связанный список, который отличается от LinkedList в Java, который является двунаправленным связанным списком. Каждый узел в связанном списке соединен указателем next, и будет указатель заголовка связанного списка и хвостовой указатель связанного списка для хранения всего связанного списка. Задача инверсии состоит в том, чтобы превратить голову -> a -> b -> c -> d d -> c -> b -> a
структура связанного списка
class Node<T> {
T value;
Node<T> next;
Node(T value) {
this.value = value;
}
}
class ReverseLinkedList<T> {
Node<T> head, tail;
}
конструктор связанного списка
Нам нужно объединить все элементы один за другим с помощью следующего указателя, а вершины головы и хвоста связанного списка должны удерживаться переменными головы и хвоста. При добавлении нового элемента необходимо скорректировать следующий указатель хвостового узла, чтобы он указывал на вновь добавленный узел элемента.
class ReverseLinkedList<T> {
private Node<T> head, tail;
public ReverseLinkedList(T... values) {
for (T value : values) {
if (tail == null) {
// 第一个节点
head = tail = new Node<>(value);
} else {
// 后面的节点往链表尾部追加
Node<T> oldTail = tail;
oldTail.next = tail = new Node<>(value);
}
}
}
}
ReverseLinkedList<Integer> l = new ReverseLinkedList<>(1,2,3,4,5,6);
Отображение содержимого связанного списка
Нам нужно предоставить метод вывода связанного списка, чтобы быстро сравнить, правильно ли содержимое связанного списка после обращения.
class ReverseLinkedList<T> {
private Node<T> head, tail;
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
Node<T> cur = head;
while (cur != null) {
sb.append(cur.value);
cur = cur.next;
if (cur != null) {
sb.append(',');
}
}
sb.append(']');
return sb.toString();
}
}
Итеративный реверсивный алгоритм
Цикл по следующему указателю — это самый простой способ думать об этом, но не так просто перевернуть указатель точно правильно. Часть цикла в приведенном ниже коде очень короткая, но очень тонкая: в ней используются три временные локальные переменные cur, next и nextnext, что может привести к ошибкам, если вы не будете осторожны.
class ReverseLinkedList<T> {
private Node<T> head, tail
public ReverseLinkedList<T> reverseByLoop() {
// 空链表或者单元素都无需处理
if (head == tail) {
return this;
}
Node<T> cur = head;
Node<T> next = cur.next;
while (next != null) {
Node<T> nextnext = next.next;
next.next = cur;
cur = next;
next = nextnext;
}
tail = head;
tail.next = null;
head = cur;
return this;
}
}
рекурсивный реверсивный алгоритм
Также неплохо использовать рекурсивное мышление для решения этой проблемы, но когда связанный список очень длинный, стек вызовов будет очень глубоким, и печально известное исключение StackOverflowException будет сгенерировано, когда связанный список увеличится до определенной степени.
class ReverseLinkedList<T> {
private Node<T> head, tail
public ReverseLinkedList<T> reverseByRecursive() {
Node<T> oldTail = tail;
tail = reverseFrom(head);
tail.next = null;
head = oldTail;
return this;
}
private Node<T> reverseFrom(Node<T> from) {
if (from == tail) {
return from;
}
Node<T> end = reverseFrom(from.next);
end.next = from;
return from;
}
}
полный код
package leetcode;
public class ReverseLinkedList<T> {
static class Node<T> {
T value;
Node<T> next;
Node(T value) {
this.value = value;
}
}
Node<T> head;
Node<T> tail;
@SafeVarargs
public ReverseLinkedList(T... values) {
for (T value : values) {
if (tail == null) {
head = tail = forNode(value);
} else {
Node<T> oldTail = tail;
oldTail.next = tail = forNode(value);
}
}
}
public ReverseLinkedList<T> reverseByLoop() {
if (head == tail) {
return this;
}
Node<T> cur = head;
Node<T> next = cur.next;
while (next != null) {
Node<T> nextnext = next.next;
next.next = cur;
cur = next;
next = nextnext;
}
tail = head;
tail.next = null;
head = cur;
return this;
}
public ReverseLinkedList<T> reverseByRecursive() {
Node<T> oldTail = tail;
tail = reverseFrom(head);
tail.next = null;
head = oldTail;
return this;
}
private Node<T> reverseFrom(Node<T> from) {
if (from == tail) {
return from;
}
Node<T> end = reverseFrom(from.next);
end.next = from;
return from;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append('[');
Node<T> cur = head;
while (cur != null) {
sb.append(cur.value);
cur = cur.next;
if (cur != null) {
sb.append(',');
}
}
sb.append(']');
return sb.toString();
}
private static <T> Node<T> forNode(T value) {
return new Node<>(value);
}
public static void main(String[] args) {
ReverseLinkedList<Integer> rl = new ReverseLinkedList<>(1, 2, 3, 4, 5, 6);
System.out.println(rl.reverseByRecursive().reverseByRecursive());
}
}