Esta nota se resolvió durante una semana entera. Espero tener información sobre la prueba escrita y la entrevista.
Este artículo contiene el siguiente contenido de la lista vinculada:
1. Creación y transversal de listas vinculadas individuales
2. Encuentre el número de nodos en una sola lista vinculada
3. Encuentre el nodo K-Last en una sola lista vinculada (Sword apunta a ofrecer, Pregunta 15)
4. Encuentre los nodos intermedios en una sola lista vinculada
5. Fusionar dos listas vinculadas individuales ordenadas, y las listas vinculadas combinadas aún están en orden [alta frecuencia de ocurrencia] (paso por la oferta, Pregunta 17)
6. La inversión de la lista unida [la frecuencia más alta de ocurrencia] (paso por la oferta, Pregunta 16)
7. Imprima una sola lista vinculada desde el final hasta el principio (Sword apunta a ofrecer, Pregunta 5)
8. Determine si una sola lista vinculada tiene un anillo
9. Saque la longitud del anillo en la lista vinculada
10. En la lista única vinculada, elimine el punto de partida del anillo (Sword apuntando a ofrecer, Pregunta 56). Esta pregunta debe usar las preguntas 8 y 9 anteriores.
11. Determine el primer punto de intersección de la intersección entre dos listas unidas (espada que apunta a ofrecer, Pregunta 37)
1. Creación y transversal de listas vinculadas individuales:
Public Class LinkList {Public Node Head; Si el nodo de encabezado está vacío, lo que significa que la lista vinculada aún no se ha creado. nodo y colóquelo en el nodo actual (correlacione el nuevo nodo con la lista vinculada) current.next = nuevo nodo (datos); /Después de completar esta operación, actualice los puntos del nodo al nodo recién agregado}} // método: atravesar la lista vinculada (imprima la lista vinculada. Los parámetros del método indican que el recorrido comienza desde la impresión de nodo public void ( Nodo nodo) {if (node == null) {return; {// NOTA: Los permisos de las dos variables de los miembros aquí no pueden ser principales porque los permisos privados solo son accesibles para esta clase; data = data; );En el código anterior, el nodo del nodo aquí usa una clase interna para representarlo (líneas 33). La mayor ventaja de usar clases internas es que pueden acceder a las operaciones privadas con clases externas.
Nota: Las características del acceso a la clase interna son: las clases internas pueden acceder directamente a los miembros de las clases externas, incluidas las clases externas privadas;
Para facilitar la adición y las operaciones transversales, agregue una corriente de variable miembro a la clase LinkList para representar el índice del nodo actual (línea 03).
En el método de atravesar la lista vinculada (línea 20), el nodo de parámetros significa que comienza desde el nodo del nodo, y no necesariamente necesita atravesar el nodo principal.
2. Encuentre el número de nodos en una sola lista vinculada:
Preste atención para verificar si la lista vinculada está vacía. La complejidad del tiempo es o (n). Esto es relativamente simple.
Código central:
// Método: Obtenga la longitud de la lista única de Public int longitud th ++;
3. Encuentre el nodo K-LaT en una sola lista vinculada:
3.1 Ideas ordinarias:
Primero, itere la lista vinculada completa de principio a fin, calcule el tamaño de longitud de la lista vinculada y obtenga la longitud de la lista vinculada, es fácil de hacer. La lista vinculada está vacía, k es 0, k es 1, k es mayor que el número de nodos en la lista vinculada
). La complejidad del tiempo es o (n), y la idea general es la siguiente:
public int FindlastNode (int index) {// El índice representa el nodo del índice al final .// La primera vez que atraviesé, obtuve la longitud de la lista vinculada si (head == null) {return -1; Current = Head; i <size - índice;¿Qué debo hacer si el entrevistador no le permite atravesar la longitud de la lista vinculada? El siguiente es.
3.2 Ideas de mejora: (esta idea también se usa en otras preguntas)
Aquí debe declarar dos punteros: es decir, las dos variables de tipo nodo primero y segundo. Primero y segundo se separa por las posiciones K-1, y luego los dos nodos se mueven hacia atrás en su conjunto hasta que el segundo nodo alcanza el último nodo, la posición señalada por el primer nodo es la posición del K-Th hasta el último nodo. La complejidad del tiempo es o (n)
Implementación del código: (primera versión)
Public Node FindLastNode (Node Head, Int Index) {if (node == NULL) {return null; 0; = Second.Next;Implementación del código: (versión final) (arroje una excepción cuando K es mayor que el número de nodos en la lista vinculada)
En el código anterior, la función parece haberse implementado, pero no es lo suficientemente robusta:
Preste atención a la situación en la que K es igual a 0;
Si K es mayor que el número de nodos en la lista vinculada, se informará una excepción de puntero nulo, por lo que se necesita un juicio aquí.
El código central es el siguiente:
Public Node FindLastNode (Node Head, int k) {if (k == 0 || head == null) {return null; posición para (int i = 0; i <k - 1; i ++) {system.out.println ("El valor de I es"+i); El valor de k ya es mayor que la longitud de la lista vinculada // arroja nueva NullPointerException ("La longitud de la lista vinculada es menor que" + K); nulo; El segundo nodo alcanza el último nodo en este momento, el nodo apuntado por primera vez es el nodo que estamos buscando.4. Encuentre los nodos intermedios en una sola lista vinculada:
Del mismo modo, el entrevistador no le permite calcular la longitud de la lista vinculada.
Idea:
Al igual que la segunda sección anterior, dos punteros se establecen primero y segundo, pero aquí, los dos punteros avanzan al mismo tiempo, el segundo puntero da dos pasos cada vez, y el primer puntero da un paso cada vez hasta que el segundo puntero llega En el último nodo, el nodo señalado por el primer puntero es el nodo intermedio. Tenga en cuenta que la lista vinculada está vacía y el número de nodos de la lista vinculada es 1 y 2. La complejidad del tiempo es o (n).
Implementación del código:
// Método: Encuentre el nodo intermedio de la lista vinculada del nodo público findMidNode (nodo de nodo) {if (head == null) {return null; Segundo final, el punto mueve dos dígitos, el primer nodo se mueve uno mientras (segundo! = NULL && SEGUNDO! Para nulo en este momento, la posición señalada por el primer puntero es la posición del retorno del nodo intermedio primero;En el código anterior, cuando n es un número uniforme, el nodo intermedio obtenido es el nodo N/2 + 1. Por ejemplo, cuando hay 6 nodos en la lista vinculada, se obtiene el cuarto nodo.
5. Fusionar dos listas unidas ordenadas, y las listas vinculadas combinadas aún están en orden:
Esta pregunta a menudo es investigada por varias compañías.
Por ejemplo:
Lista 1:
1-> 2-> 3-> 4
Lista 2:
2-> 3-> 4-> 5
Después de la fusión:
1-> 2-> 2-> 3-> 3-> 4-> 4-> 5
Idea de solución:
Compare la lista vinculada 1 y la lista vinculada 2 uno al lado del otro.
Esto es similar a la clasificación de fusiones. Preste especial atención a la situación en la que ambas listas vinculadas están vacías y una de ellas está vacía. Solo se requiere espacio o (1) espacio. La complejidad del tiempo es O (Max (Len1, Len2))
Implementación del código:
// Los dos parámetros representan los nodos de encabezado de las dos listas vinculadas del nodo público MergelinkList (nodo head1, nodo head2) {if (head1 == null && head2 == null) {// if (head1 == null) {return feaT2; Lista // Al principio, dejamos que el nodo actual apunte a los datos más pequeños en Head1 y Head2, y obtenga el nodo de cabeza if (head1.data <head2.data) {head = head = cotent = head1; Siguiente; ;/ Current.next; (head2! = null) {// indica que la lista vinculada 1 después de atravesar, está vacía.next = head2;Prueba de código:
public static void main (string [] args) {LinkList list1 = new LinkList (); (i); ); /Fusionar list1 y list2 y almacenarlo en list3 list3.print (list3.head);El método Agregar y el método de impresión utilizado en el código anterior son consistentes con la subsección 1.
Efecto de ejecución:
Nota: La solución es recursiva en la "oferta de apuntación de espadas", que se siente un poco difícil de entender.
6. Inversión de la lista de un solo ligero: [la frecuencia más alta de ocurrencia]
Por ejemplo, lista vinculada:
1-> 2-> 3-> 4
Después de la inversión:
4-> 2-> 2-> 1
Idea:
Itere a través de la lista vinculada original de principio a fin, y cada nodo se atraviesa, y se elimina y se coloca en el extremo frontal de la nueva lista vinculada. Tenga en cuenta que la lista vinculada está vacía y solo hay un nodo. La complejidad del tiempo es o (n)
Método 1: (transversal)
// Método: Reversión de la lista vinculada Reverselista de nodo público (cabezal de nodo) {// Si la lista vinculada está vacía o solo hay un nodo, no se requiere inversión, y el nodo principal de la lista vinculada original se devuelve directamente al Lista vinculada IF (head == NULL || El encabezado de la nueva lista vinculada después de la inversión (actual! = NULL) {next = current.next; Siguiente nodo de corriente al nodo de encabezado de la nueva lista vinculada reversa = corriente;En el código anterior, el código central es las líneas 16 y 17.
Método 2: (recursión)
Este método es un poco difícil, por lo que no hablaré de ello por ahora.
7. Imprima una sola lista vinculada de extremo a extremo:
Para este tipo de orden invertido, debemos pensar en Stack, primero en y primera vez. Por lo tanto, esta pregunta usa la pila usted mismo o permite que el sistema use la pila, es decir, recursiva. Presta atención al caso donde la lista vinculada está vacía. La complejidad del tiempo es o (n)
Nota: No piense primero en revertir la lista única vinculada y luego atravesar la salida.
Método 1: (crea una nueva pila por ti mismo)
// Método: imprima una sola lista vinculada desde el final hasta el final Void ReversePrint (Node Head) {if (head == NULL) {return; Cree un nuevo nodo de pila curry = head; // Presione la pila que el nodo se imprime mientras (stack.size ()> 0) {system.out.println (stack.pop (). Data);Método 2: (Use la pila del sistema: código recursivo, elegante y conciso)
public void reverseprint (nodo head) {if (head == null) {return;Resumen: el método 2 se basa en la implementación de la recursión. La pila explícita del método 1 se implementa en función de los bucles, y el código es más robusto.
8. Determine si una sola lista vinculada tiene un anillo:
Aquí también se usan dos punteros.
Por lo tanto, usamos dos punteros para atravesar: el primer puntero da un paso a la vez, y el segundo puntero da dos pasos a la vez. La complejidad del tiempo es o (n).
método:
// Método: determine si una sola lista vinculada tiene un anillo de húsico booleano (cabezal de nodo) {if (head == null) {return false; ) {Primero = primero.next; un anillo return verdadero;Código de versión completo: (incluida la parte de prueba)
Aquí, también necesitamos agregar un método ADD (nodo de nodo) sobrecargado, que debe usarse al crear una lista circular vinculada de un solo sentido.
Linklist.java: public class Linklist {cabezal de nodo público; ll) { / /Si el nodo de encabezado está vacío, significa que la lista vinculada aún no se ha creado, luego asigne el nuevo nodo al cabezal del nodo del encabezado = nuevo nodo (datos); Cree un nuevo nodo, colóquelo detrás del nodo actual (correlacione el nuevo nodo con la lista vinculada) current.next = nuevo nodo (datos); ; ; Nodo nodo) {if (node == null) {return; Método: Detectar si una sola lista vinculada tiene un anillo de húsico booleano (n Ode) {if (head == null) {return false; Primero = primero.next; La lista tiene un anillo return verdadero; INT DATOS ;/ Agregue datos a LinkList para (int i = 0; i <4; i ++) {list.add (i); es un bucle en la lista vinculada. Nota: La estructura del anillo obtenida en este momento es la estructura de la Figura 1 en la siguiente sección 8. System.out.println (list.hascycle (list.head));El código que detecta si una sola lista vinculada tiene un anillo es la línea 50.
Línea 88: Continuamos agregando el nodo de encabezado a la lista vinculada, y la lista vinculada única se bucle en este momento. El efecto de carrera final es verdadero.
Si se eliminan 88 líneas de código, la lista única vinculada no tiene bucles en este momento, y el efecto de ejecución es falso.
9. Saque la lista vinculada al anillo, la longitud del anillo:
La lista de enlaces que generalmente encontramos es la siguiente: (Figura 1)
La longitud del anillo en la imagen de arriba es 4.
Pero es posible que lo siguiente sea también lo siguiente: (Figura 2)
En este momento, la longitud del anillo en la imagen de arriba es 3.
Entonces, ¿cómo encuentras la longitud del anillo?
Idea:
Aquí, primero debemos usar el método de húsico en la sección 7 anterior (el método para determinar si hay un anillo en la lista vinculada). Devuelve el valor del nodo donde nos encontramos. Luego, podemos obtener el nodo donde nos encontramos.
método:
// Método: determine si una sola lista vinculada tiene un anillo. El nodo devuelto es el nodo donde se encuentra con el nodo público (cabezal de nodo) {if (head == null) {return null; .Next; NULL; El nodo de parámetro representa el nodo donde se encuentra con el público int getCyCleleng. Current.next;Código de versión completo: (incluida la parte de prueba)
Public Class LinkList {Public Node Head; El nodo está vacío, significa que la lista vinculada aún no se ha creado, luego asigne el nuevo nodo al cabezal del nodo de encabezado = nuevo nodo (data); El nodo actual (correlacione el nuevo nodo con la lista vinculada) current.next = new Node (datos); El nodo actual apunta al nodo recién agregado}} // sobrecarga del método: agregue el nodo a la lista vinculada public void add (nodo nodo) {if (node == null) {return; {head = node; Desde el nodo publicitario de nodo (nodo de nodo) {if (node == null) {return; Current.next; Primero = nodo segundo = While (segundo! = La lista vinculada es una devolución de anillo primero; El nodo de parámetro representa el nodo donde se encuentra con el público int getCyCleleng. Current.next; Privado, porque los permisos de privado solo son accesibles para esta clase. INT DATOS ;/ = NULL; ; /Corta el segundo nodo}} list1.add (segundo); El proceso es la estructura de la Figura 2 en esta sección nodo corriente = list1.hascycle (list1.head); ));Efecto de ejecución:
Si el código de prueba anterior de las líneas 104 a 122 se cambia a lo siguiente: (es decir, cambie la estructura en la Figura 2 a la estructura de la Figura 1)
public static void main (string [] args) {LinkList list1 = new LinkList (); (list1.head); Nota: La estructura de este anillo obtenida en este momento es la estructura de la Figura 1 en esta sección. Nodo corriente = list1.hascycle (list1.head);Ejecutar resultados:
Si elimina la octava línea en el código anterior, entonces la lista vinculada no tiene bucles, por lo que el resultado de ejecutar es 0.
10. En la lista única vinculada, el punto de partida del anillo extraído:
La lista de enlaces que generalmente encontramos es la siguiente: (Figura 1)
El punto de inicio 1 del anillo en la imagen de arriba.
Pero es posible que lo siguiente sea también lo siguiente: (Figura 2)
En este momento, el punto de partida del anillo en la imagen de arriba es 2.
Método 1:
Aquí debemos usar el método para eliminar la longitud del anillo en la sección 8 anterior para getCyclelength, y usar este método para obtener la longitud del anillo. Después de obtener la longitud del anillo, se deben usar dos variables de puntero. Encuentra, el nudo cuando se encuentran.
Nota: Para encontrar el punto de partida del anillo, primero debemos obtener la longitud del anillo, y para obtener la longitud del anillo, primero debemos determinar si hay un anillo. Entonces, en realidad, hay tres métodos utilizados aquí.
Implementación del código:
Código central para el método 1:
// Método: obtenga el punto de inicio del anillo. La longitud del parámetro representa la longitud del nodo público de anillo getCyclStart (nodo de nodo, int cyclelath) {if (head == null) {return null; al paso de longitud para (int i = 0; i <cyclelength; i ++) {segundo = segundo.next; ! = null) {first = first.next; regresar nulo;Código de versión completo: (incluida la parte de prueba)
Public Class LinkList {Public Node Head; El nodo está vacío, significa que la lista vinculada aún no se ha creado, luego asigne el nuevo nodo al cabezal del nodo de encabezado = nuevo nodo (data); El nodo actual (correlacione el nuevo nodo con la lista vinculada) current.next = new Node (datos); El nodo actual apunta al nodo recién agregado}} // sobrecarga del método: agregue el nodo a la lista vinculada public void add (nodo nodo) {if (node == null) {return; {head = node; Desde el nodo publicitario de nodo (nodo de nodo) {if (node == null) {return; Current.next; Primero = nodo segundo = While (segundo! = La lista vinculada es una devolución de anillo primero; El nodo de parámetro representa el nodo donde se encuentra con el público int getCyCleleng. Current.next; La longitud del parámetro representa la longitud del nodo público de anillo getCyclStart (nodo de nodo, int cyclelath) {if (head == null) {return null; al paso de longitud para (int i = 0; i <cyclelength; i ++) {segundo = segundo.next; ! = null) {first = first.next; return null; INT DATOS ;/ = NULL; ; /Corta el segundo nodo}} list1.add (segundo); El tiempo es la estructura de la Figura 2 en esta sección de nodo Corriente = list1.hascycle (list1.head); .out.println ("El punto de inicio del anillo es" + list1.getCyClStart (list1.head, longitud) .data);11. Determine el primer punto de intersección donde se cruzan dos listas ligadas:
"La belleza de la programación" P193, 5.3, la pregunta de la entrevista 37 tiene esta pregunta.
Durante la entrevista, la primera reacción de muchas personas al encontrar esta pregunta es: atravesar cada nodo en secuencia en la primera lista vinculada. Si hay un nodo en la segunda lista vinculada igual que el nodo en la primera lista vinculada, significa que las dos listas vinculadas se superponen en este nodo. Obviamente, la complejidad del tiempo de este método es O (len1 * len2).
Método 1: la idea de usar pila
Podemos ver dos listas vinculadas con nodos comunes y parcialmente superpuesto, la forma topológica parece una Y, pero no puede ser una en forma de X. Como se muestra en la figura a continuación:
Como se muestra en la figura anterior, si una sola lista vinculada tiene un nodo común, entonces el último nodo (nodo 7) debe ser el mismo, y comienza desde cierto nodo en el medio (nodo 6) y Los nodos posteriores son los mismos.
El problema ahora es que en una sola lista vinculada, solo podemos atravesar la secuencia desde los nodos iniciales y finalmente llegar al nodo final. El nodo de cola final que alcanza se compara primero. Por lo tanto, podemos pensar en usar las características de la pila para resolver este problema: coloque los nodos de las dos listas vinculadas en dos pilas, de modo que los nodos finales de las dos listas vinculadas se encuentran en la parte superior de las dos pilas a continuación. Comparemos.
De esta manera, necesitamos usar dos pilas auxiliares, la complejidad del espacio es O (len1+len2) y la complejidad del tiempo es O (len1+len2). En comparación con el método de fuerza bruta al principio, se ha mejorado la eficiencia del tiempo, lo que es equivalente al uso del consumo de espacio para la eficiencia del tiempo.
Entonces, ¿hay una mejor manera? Hablemos de eso a continuación.
Método 2: Determine el primer nodo donde se cruzan dos listas vinculadas: use el puntero rápido y lento, recomendado (solución más óptima)
En el método 2 anterior, la razón por la que usamos la pila es porque queremos atravesar para alcanzar los nodos finales de las dos listas vinculadas al mismo tiempo.其实为解决这个问题我们还有一个更简单的办法：首先遍历两个链表得到它们的长度。在第二次遍历的时候，在较长的链表上走|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链表的经典面试题目，希望可以帮助大家顺利通过面试。