Esta nota foi resolvida por uma semana inteira. Espero ter algumas informações sobre o teste e a entrevista por escrito.
Este artigo contém o seguinte conteúdo da lista vinculada:
1. Criação e travessia de listas vinculadas únicas
2. Encontre o número de nós em uma única lista vinculada
3. Encontre o nó K-Last em uma única lista vinculada (apontando a espada para oferecer, pergunta 15)
4. Encontre os nós intermediários em uma única lista vinculada
5. Mesclar duas listas vinculadas únicas ordenadas, e as listas vinculadas combinadas ainda estão em ordem [alta frequência de ocorrência] (passo pela oferta, pergunta 17)
6. A reversão da lista de ligações únicas [a maior frequência de ocorrência] (passo pela oferta, pergunta 16)
7. Imprima uma única lista vinculada do final ao início (espada apontando para oferecer, pergunta 5)
8. Determine se uma única lista vinculada tem um anel
9. Tire o comprimento do anel na lista vinculada
10. Na lista única vinculada, retire o ponto de partida do anel (espada apontando para oferecer, pergunta 56). Esta pergunta precisa usar as perguntas 8 e 9 acima.
11. Determine o primeiro ponto de interseção da interseção entre duas listas de ligamento único (apontando a espada a oferecer, pergunta 37)
1. Criação e travessia de listas vinculadas únicas:
classe pública Linklist {Public Node Head; Se o nó do cabeçalho está vazio, o que significa que a lista vinculada ainda não foi criada. Nó e coloque -o no nó atual (correlacione o novo nó com a lista vinculada) Current.Next = NODE (Data); /Após a conclusão desta operação, atualize o nó aponta para o nó recém -adicionado}} // Método: Travesse a lista vinculada (imprima a lista vinculada. Os parâmetros do método indicam que a travessia começa a partir do nó public void de nó. Nó) {if (node == null) {return; {// NOTA: As permissões das duas variáveis de membro aqui não podem ser prateadas porque as permissões privadas são acessíveis apenas a esta classe. Dados = dados; );No código acima, o nó aqui usa uma classe interna para representá -lo (linhas 33). A maior vantagem do uso de classes internas é que elas podem acessar as operações privadas com classes externas.
Nota: As características do acesso à classe interna são: Classes internas podem acessar diretamente os membros de classes externas, incluindo as classes externas;
Para facilitar as operações de adição e travessia, adicione uma corrente de variável de membro à classe Linklist para representar o índice do nó atual (linha 03).
No método de percorrer a lista vinculada (linha 20), o nó do parâmetro significa que ele começa no nó do nó e não precisa necessariamente atravessar do nó da cabeça.
2. Encontre o número de nós em uma única lista vinculada:
Preste atenção para verificar se a lista vinculada está vazia. A complexidade do tempo é O (n). Isso é relativamente simples.
Código central:
// Método: Obtenha o comprimento da lista única Public Int GetLength (cabeça de nó) {if (head == null) {return 0; comprimento th ++;3. Encontre o nó K-Last em uma única lista vinculada:
3.1 Idéias comuns:
Primeiro, itera toda a lista vinculada do começo ao fim, calcule o tamanho do comprimento da lista vinculada e obtenha o comprimento da lista vinculada, é fácil de fazer. A lista vinculada está vazia, k é 0, k é 1, k é maior que o número de nós na lista vinculada
). A complexidade do tempo é O (n), e a idéia geral é a seguinte:
public int findLastNode (int index) {// ÍNDICE representa o nó do índice até o final. Current = Head; i <tamanho - índice;O que devo fazer se o entrevistador não permitir que você atravesse a duração da lista vinculada? O próximo é.
3.2 Idéias de melhoria: (Esta ideia também é usada em outras perguntas)
Aqui você precisa declarar dois ponteiros: ou seja, as duas variáveis do tipo nó primeiro e o segundo. O primeiro e o segundo é separado por posições de K-1 e, em seguida, os dois nós são movidos para trás como um todo até que o segundo nó atinja o último nó, a posição apontada pelo primeiro nó é a posição do K-é nó. A complexidade do tempo é O (n)
Implementação de código: (primeira versão)
nó público findLastNode (cabeça de nó, int index) {if (node == null) {return null; 0; = Second.Next;Implementação de código: (versão final) (jogue uma exceção quando k for maior que o número de nós na lista vinculada)
No código acima, a função parece ter sido implementada, mas não é robusta o suficiente:
Preste atenção à situação em que K é igual a 0;
Se K for maior que o número de nós na lista vinculada, uma exceção de ponteiro nulo será relatada, portanto, é necessário um julgamento aqui.
O código principal é o seguinte:
nó público findLastNode (cabeça de nó, int k) {if (k == 0 || head == null) {return null; Posição para (int i = 0; i <k - 1; i ++) {System.out.println ("I's Valor é"+i); O valor de k já é maior que o comprimento da lista vinculada // lança nova nullpointerException ("O comprimento da lista vinculado é menor que" + k); nulo; O segundo nó atinge o último nó neste momento, o nó apontado pela primeira vez é o nó que estamos procurando.4. Encontre os nós intermediários em uma única lista vinculada:
Da mesma forma, o entrevistador não permite que você calcule o comprimento da lista vinculada.
Ideia:
Como a segunda seção acima, dois ponteiros são definidos em primeiro e segundo, mas aqui, os dois ponteiros avançam ao mesmo tempo, o segundo ponteiro dá dois passos de cada vez, e o primeiro ponteiro dá um passo a cada vez que o segundo ponteiro chegar No último nó, o nó apontado pelo primeiro ponteiro é o nó intermediário. Observe que a lista vinculada está vazia e o número de nós da lista vinculada é 1 e 2. A complexidade do tempo é O (n).
Implementação de código:
// Método: Encontre o nó intermediário da lista vinculada Public Node FindMidnode (cabeça do nó) {if (Head == NULL) {Retorno NULL; Segunda final, o ponto se move dois dígitos, o primeiro nó se move um enquanto (segundo! = null && segundo.next! Neste momento, a posição apontada pelo primeiro ponteiro é a posição do Nó Intermediário Retorno primeiro;No código acima, quando n é um número par, o nó intermediário obtido é nó n/2 + 1. Por exemplo, quando existem 6 nós na lista vinculada, o quarto nó é obtido.
5. Mesclar duas listas de ligações únicas ordenadas, e as listas vinculadas combinadas ainda estão em ordem:
Esta questão é frequentemente investigada por várias empresas.
Por exemplo:
Lista 1:
1-> 2-> 3-> 4
Lista 2:
2-> 3-> 4-> 5
Após a mesclagem:
1-> 2-> 2-> 3-> 3-> 4-> 4-> 5
Ideia da solução:
Compare a lista 1 vinculada e a lista 2 vinculada um ao lado do outro.
Isso é semelhante à classificação de mesclagem. Preste atenção especial à situação em que as duas listas vinculadas estão vazias e uma delas está vazia. Somente O (1) é necessário espaço. A complexidade do tempo é O (Max (Len1, Len2))
Implementação de código:
// Os dois parâmetros representam os nós do cabeçalho das duas listas vinculadas MergelinkList (nó head1, nó head2) {if (head1 == null && head2 == null) {// se as duas listas vinculadas estiverem vazias, retornar nulo; if (Head1 == NULL) {Retorno Head2; Lista // No início, deixamos o nó atual apontar para os dados menores em Head1 e Head2 e obtemos o nó da cabeça se (Head1.data <Head2.Data) {Head = Head1; Em seguida; ; atual.Next; (Head2! = NULL) {// Indique que a lista 1 vinculada após a travessia, está vazia.Next = Head2;Teste de código:
public static void main (string [] args) {linklist list1 = new Linklist (); (i); );O método ADD e o método de impressão usado no código acima são consistentes com a subseção 1.
Efeito de corrida:
NOTA: A solução é recursiva na "oferta de ponta de espada", que parece um pouco difícil de entender.
6. Inversão da lista de ligações únicas: [a maior frequência de ocorrência]
Por exemplo, lista vinculada:
1-> 2-> 3-> 4
Após a inversão:
4-> 2-> 2-> 1
Ideia:
Itera através da lista vinculada original do começo ao fim, e cada nó é atravessado e é removido e colocado na extremidade frontal da nova lista vinculada. Observe que a lista vinculada está vazia e há apenas um nó. A complexidade do tempo é O (n)
Método 1: (Traversal)
// Método: reversão da lista vinculada Reverselista de nós públicos (cabeça do nó) {// Se a lista vinculada estiver vazia ou houver apenas um nó, nenhuma inversão é necessária e o nó da cabeça da lista vinculada original é retornada diretamente ao LISTA LING ORIGINAL IF (Head == NULL || HEAD.NEXT == NULL) {Retorno Head; O cabeçalho da nova lista vinculada após a inversão (atual! = NULL) {Next = Current.Next; Nó próximo de corrente para o nó do cabeçalho da nova lista vinculada Reversehead = Current;No código acima, o código principal são as linhas 16 e 17.
Método 2: (Recursão)
Esse método é um pouco difícil, então não vou falar sobre isso por enquanto.
7. Imprima uma única lista vinculada de ponta a ponta:
Para esse tipo de ordem invertida, devemos pensar em Stack, primeiro dentro e primeiro a sair. Portanto, essa pergunta usa a pilha ou permite que o sistema use a pilha, ou seja, recursiva. Preste atenção ao caso em que a lista vinculada está vazia. A complexidade do tempo é O (n)
Nota: não pense em reverter a lista única vinculada e depois atravessar a saída.
Método 1: (Crie uma nova pilha sozinha)
// Método: Imprima uma única lista vinculada do final até o final public void reverseprint (cabeça do nó) {if (head == null) {return; Crie um novo nó de pilha Rent = Head; // Pressione a pilha O nó imprime (Stack.size ()> 0) {System.out.println (Stack.pop (). Dados);Método 2: (Use a pilha do sistema: código recursivo, elegante e conciso)
public void reverseprint (cabeça do nó) {if (head == null) {return;Resumo: O método 2 é baseado na implementação da recursão. A pilha explícita do método 1 é implementada com base em loops e o código é mais robusto.
8. Determine se uma única lista vinculada tem um anel:
Dois ponteiros também são usados aqui.
Portanto, usamos dois ponteiros para atravessar: o primeiro ponteiro dá um passo de cada vez, e o segundo ponteiro dá duas etapas por vez. A complexidade do tempo é O (n).
método:
// Método: Determine se uma única lista vinculada possui um anel publicitário hasco booleano (cabeça do nó) {if (head == null) {return false; ) {primeiro = primeiro.next; um anel retorno verdadeiro;Código da versão completa: (incluindo a parte de teste)
Aqui, também precisamos adicionar um método ADD (nó) sobrecarregado (nó), que deve ser usado ao criar uma lista vinculada circular unidirecional.
Linklist.java: public class linklist {public node head; ll) { / /Se o nó do cabeçalho estiver vazio, isso significa que a lista vinculada ainda não foi criada e atribua o novo nó ao nó do cabeçalho = novo nó (dados); Crie um novo nó, coloque -o por trás do nó atual (correlacione o novo nó com a lista vinculada) Current.Next = novo nó (dados); ; } else {current.n ext = node; Nó) {if (node == null) {return; Método: Detectar se uma única lista vinculada possui um anel publicitário hasco booleano (n ode head) {if (head == null) {return false; primeiro = primeiro.next; Lista possui um retorno anel true; Dados int; Adicione dados ao linklist para (int i = 0; i <4; i ++) {list.add (i); é um loop na lista vinculada. Nota: A estrutura do anel obtida neste momento é a estrutura da Figura 1 na seção 8 a seguir. System.out.println (list.hascycle (list.head));O código que detecta se uma única lista vinculada possui um anel é a linha 50.
Linha 88: Continuamos a adicionar o nó do cabeçalho à lista vinculada, e a lista vinculada única será emitida neste momento. O efeito final de corrida é verdadeiro.
Se 88 linhas de código forem excluídas, a lista vinculada única não possui loops no momento e o efeito de execução será falso.
9. Retire a lista ligada ao anel, o comprimento do anel:
A lista de links que geralmente encontramos é a seguinte: (Figura 1)
O comprimento do anel na figura acima é 4.
Mas é possível que o seguinte também seja o seguinte: (Figura 2)
Neste momento, o comprimento do anel na figura acima é 3.
Então, como você encontra o comprimento do anel?
Ideia:
Aqui, precisamos primeiro usar o método Hascycle na seção 7 acima (o método para determinar se existe um anel na lista vinculada). Retorna o valor para o nó onde nos encontramos. Então, podemos obter o nó onde nos encontramos.
método:
// Método: determine se uma única lista vinculada possui um anel. O nó retornado é o nó onde atende a um nó público (cabeça de nó) {if (head == null) {return null; .next; NULL; O nó do parâmetro representa o nó onde atende a public Int GetCycleLey (nó) {if (head == null) {return 0; Current.Next;Código da versão completa: (incluindo a parte de teste)
classe pública Linklist {Public Node Head; O nó está vazio, significa que a lista vinculada ainda não foi criada e atribua o novo nó ao nó cabeçalho da cabeça = novo nó (dados); o nó atual (correlaciona o novo nó com a lista vinculada) Current.Next = novo nó (dados); O nó atual aponta para o nó recém -adicionado}} // sobrecarga do método: Adicione o nó à lista vinculada public void add (nó nó) {if (node == null) {return; {Head = Node; A partir do nó public nó node (nó) {if (node == null) {return; Current.Next; Primeiro = cabeça; Lista vinculada é um retorno de anel primeiro; O nó do parâmetro representa o nó onde atende a public Int GetCycleLey (nó) {if (head == null) {return 0; Current.Next; Privado, porque as permissões de privado são acessíveis apenas a esta classe. Dados int; // Nó de dados Avançar; = null; ; O processo é a estrutura da Figura 2 nesta seção Current = list1.hascycle (list1.head); ));Efeito de corrida:
Se o código de teste acima das linhas 104 a 122 for alterado para o seguinte: (ou seja, altere a estrutura na Figura 2 para a estrutura na Figura 1)
public static void main (string [] args) {linklist list1 = new Linklist (); (list1.head); Nota: A estrutura deste anel obtida neste momento é a estrutura da Figura 1 nesta seção. Node Current = List1.hascycle (list1.head);Execute os resultados:
Se você excluir a 8ª linha no código acima, a lista vinculada não terá loops, portanto, o resultado da execução é 0.
10. Na lista única vinculada, o ponto de partida do anel extraído:
A lista de links que geralmente encontramos é a seguinte: (Figura 1)
O ponto de partida 1 do anel na figura acima.
Mas é possível que o seguinte também seja o seguinte: (Figura 2)
Neste momento, o ponto de partida do anel na figura acima é 2.
Método 1:
Aqui, precisamos usar o método de tirar o comprimento do anel na Seção 8 acima para obter o comprimento e usar esse método para obter o comprimento do anel. Depois de obter o comprimento do anel, duas variáveis de ponteiro precisam ser usadas. Conheça, o nó quando eles se encontrarem.
Nota: Para encontrar o ponto de partida do anel, precisamos primeiro obter o comprimento do anel e, para obter o comprimento do anel, precisamos primeiro determinar se existe um anel. Portanto, existem realmente três métodos usados aqui.
Implementação de código:
Código principal do método 1:
// Método: Obtenha o ponto de partida do anel. O comprimento do parâmetro representa o comprimento do nó público getCyclestart (cabeça de nó, int cicleling) {if (head == null) {return null; à etapa do comprimento para (int i = 0; i <cycleLength; i ++) {Second = Second.Next; ! = NULL) {primeiro = primeiro.Next; retornar nulo;Código da versão completa: (incluindo a parte de teste)
classe pública Linklist {Public Node Head; O nó está vazio, significa que a lista vinculada ainda não foi criada e atribua o novo nó ao nó cabeçalho da cabeça = novo nó (dados); o nó atual (correlaciona o novo nó com a lista vinculada) Current.Next = novo nó (dados); O nó atual aponta para o nó recém -adicionado}} // sobrecarga do método: Adicione o nó à lista vinculada public void add (nó nó) {if (node == null) {return; {Head = Node; A partir do nó public nó node (nó) {if (node == null) {return; Current.Next; Primeiro = cabeça; Lista vinculada é um retorno de anel primeiro; O nó do parâmetro representa o nó onde atende a public Int GetCycleLey (nó) {if (head == null) {return 0; Current.Next; O comprimento do parâmetro representa o comprimento do nó público getCyclestart (cabeça de nó, int cicleling) {if (head == null) {return null; à etapa do comprimento para (int i = 0; i <cycleLength; i ++) {Second = Second.Next; ! = NULL) {primeiro = primeiro.Next; Retorne nulo;} Nó da classe {// Nota: esta as permissões das duas variáveis de membro no momento não podem ser privadas, porque as permissões de privado só são acessíveis a esta classe. Dados int; // Nó de dados Avançar; = null; ; O tempo é a estrutura da Figura 2 nesta seção Current = list1.hascycle (list1.head); .out.println ("O ponto de partida do anel é" + list1.getCyclestart (list1.head, comprimento) .data);11. Determine o primeiro ponto de interseção em que duas listas de ligação única se cruzam:
"A beleza da programação" p193, 5.3, a pergunta da entrevista 37 tem essa pergunta.
Durante a entrevista, a primeira reação de muitas pessoas ao encontrar esta pergunta é: atravessar cada nó em sequência na primeira lista vinculada. Se houver um nó na segunda lista vinculada da mesma forma que o nó na primeira lista vinculada, significa que as duas listas vinculadas se sobrepõem neste nó. Obviamente, a complexidade do tempo desse método é O (Len1 * len2).
Método 1: A ideia de usar a pilha
Podemos ver duas listas vinculadas com nós comuns e parcialmente sobrepostos, a forma topológica parece um Y, mas não pode ser em forma de X. Como mostrado na figura abaixo:
Como mostrado na figura acima, se uma única lista vinculada tiver um nó comum, o último nó (nó 7) deve ser o mesmo, e começa a partir de um certo nó no meio (nó 6) e Os nós subsequentes são os mesmos.
O problema agora é que, em uma única lista vinculada, só podemos atravessar em sequência desde os nós iniciais e finalmente atingir o nó final. O nó final da cauda que atinge o primeiro é comparado. Portanto, podemos pensar em usar as características da pilha para resolver esse problema: coloque os nós das duas listas vinculadas em duas pilhas, para que os nós finais das duas listas vinculadas estejam localizadas na parte superior das duas pilhas. Vamos comparar.
Dessa forma, precisamos usar duas pilhas auxiliares, a complexidade do espaço é O (Len1+Len2) e a complexidade do tempo é O (Len1+Len2). Comparado com o método de força bruta no início, a eficiência do tempo foi aprimorada, o que equivale a usar o consumo de espaço para a eficiência do tempo.
Então, existe uma maneira melhor? Vamos falar sobre isso a seguir.
Método 2: Determine o primeiro nó em que duas listas vinculadas se cruzam: use o ponteiro rápido e lento, recomendado (solução mais ideal)
No método 2 acima, a razão pela qual usamos a pilha é porque queremos atravessar para alcançar os nós finais das duas listas vinculadas ao mesmo tempo.其实为解决这个问题我们还有一个更简单的办法：首先遍历两个链表得到它们的长度。在第二次遍历的时候，在较长的链表上走|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链表的经典面试题目，希望可以帮助大家顺利通过面试。