Compartir tecnología

Preguntas seleccionadas de la prueba de superficie de Likou y Niukelian

2024-07-12

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

💎 欢迎各位大佬互三：mi página de inicio

1. Lista enlazada inversa

206.Lista enlazada inversa

Pensamiento: si no abre espacio adicional y solo modifica la lista vinculada original, ¿qué método se debe utilizar?

Simplemente comience desde el segundo elemento y realice la inserción del cabezal en secuencia.

Luego simplemente modifique la referencia y apunte el último elemento a nulo

  1. class Solution {
  2.     public ListNode reverseList(ListNode head) {
  3.         //head为null，直接返回
  4.         if(head == null){
  5.             return head;
  6.         }
  7.  
  8.         ListNode cur = head.next;
  9.         //head变为了末尾元素，指向null
  10.         head.next = null;
  11.         while(cur!=null){
  12.             //curn为cur的next节点，便于往后移动
  13.             ListNode curn = cur.next;    
  14.             cur.next = head;
  15.             head = cur;
  16.             //更新cur
  17.             cur = curn;
  18.         }
  19.         return head;
  20.     }
  21. }

2. El nodo medio de la lista vinculada.

876. Nodo intermedio de lista enlazada

El primer método que me viene a la mente para esta pregunta es definitivamente definir un cnt, recorrer la lista vinculada una vez, luego encontrar el número del medio y luego recorrer el valor de retorno. Este método es muy simple, pero ¿qué sucede si necesita atravesar el? ¿Lista vinculada solo una vez para encontrar el nodo intermedio?

Aquí hay una nueva idea: use los punteros rápido y lento, comenzando desde la cabeza. El puntero rápido mueve dos nodos cada vez y el puntero lento mueve un nodo cada vez.

Entonces implementémoslo:

  1. class Solution {
  2.     public ListNode middleNode(ListNode head) {
  3.         if(head == null){
  4.             return null;
  5.         }
  6.         ListNode fast = head;
  7.         ListNode slow = head;
  8.         while(fast!= null&&fast.next!= null){
  9.             fast = fast.next.next;
  10.             slow = slow.next;
  11.         }
  12.         return slow;
  13.     }
  14. }

¿Sería esto más eficiente?

3. Devuelve el k-ésimo nodo del último

Pregunta de la entrevista 02.02. Devuelve el k-ésimo nodo del último.

Lo primero que me viene a la mente para esta pregunta es recorrerlo una vez para obtener la longitud total y luego encontrar el k-ésimo nodo del último. Sin embargo, con la base de la pregunta anterior, puedes pensar en otro método: Similarmente,Usando los punteros rápido y lento, deje ir rápido los nodos k-1 primero, y luego lento y rápido al mismo tiempo. Cuando el siguiente de rápido es nulo, significa que rápido ha llegado al último nodo y lento en este momento. es el k-ésimo nodo desde abajo.

Esta pregunta indica que la entrada k es legal, por lo que no se necesita ningún juicio adicional sobre cómo juzgar si k es ilegal, y se requiere que la longitud de la lista vinculada no se pueda encontrar directamente, por lo que es necesario juzgar lentamente mientras se camina.

  1. class Solution {
  2.     public int kthToLast(ListNode head, int k) {
  3.         if (head == null) {
  4.             return -1;
  5.         }
  6.         ListNode fast = head;
  7.         ListNode slow = head;
  8.         int cnt = 0;
  9.         while (cnt != k - 1) {
  10.             //判断k的合法性，虽然本题不用判断
  11.             fast = fast.next;
  12.             if(fast == null){
  13.                 return;
  14.             }
  15.             cnt++;
  16.         }
  17.         //slow和fast同时移动
  18.  
  19.         while (fast.next != null) {
  20.             fast = fast.next;
  21.             slow = slow.next;
  22.         }
  23.         return slow.val;
  24.     }
  25. }

4. Fusionar listas enlazadas

21. Fusionar dos listas enlazadas ordenadas

Idea:Solo necesita definir un nuevo nodo newH y luego comparar el valor de headA y headB. Para finalmente encontrar el nodo principal de la lista vinculada fusionada, también debe definir un tmp = newH, y luego el que tenga el más pequeño. tmp.next lo señalará.

  1. class Solution {
  2.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  3.         ListNode head = new ListNode();
  4.         ListNode tmp = head;
  5.     
  6.         while(list1!=null&&list2!=null){
  7.             if(list1.val < list2.val){
  8.                 tmp.next = list1;
  9.                 list1 = list1.next;
  10.                 tmp = tmp.next;
  11.             }else{
  12.                 tmp.next = list2;
  13.                 list2 = list2.next;
  14.                 tmp = tmp.next;
  15.             }
  16.         }
  17.         //判断剩余的情况
  18.         if(list1!=null){
  19.             tmp.next = list1;
  20.         }else if(list2!=null){
  21.             tmp.next = list2;
  22.         }
  23.         return head.next;
  24.     }
  25. }

5. División de lista vinculada

División de lista vinculada CM11

Esta es una pregunta de una entrevista sobre Niuke. El significado de la pregunta es dividir la lista vinculada. El lado izquierdo de x es menor que x y el lado derecho es mayor que x.

Idea: defina un nuevo nodo cur para recorrer la lista vinculada original (para evitar que se cambie la lista vinculada original), coloque todo lo que sea mayor que x en una lista vinculada, coloque todo lo que sea menor que x en una lista vinculada y finalmente conecte los dos listas enlazadas.

  1. public class Partition {
  2.     public ListNode partition(ListNode pHead, int x) {
  3.         ListNode bs = null;
  4.         ListNode be = null;
  5.         ListNode as = null;
  6.         ListNode ae = null;
  7.         ListNode cur = pHead;
  8.         while (cur != null) {
  9.             if (cur.val < x) {
  10.                 //处理刚开始为null的情况
  11.                 if (bs == null) {
  12.                     bs = be = cur;
  13.                 }else{
  14.                     be.next = cur;
  15.                     be = be.next;
  16.                 }
  17.             }else{
  18.                 if(as == null){
  19.                     as = ae = cur;
  20.                 }else{
  21.                     ae.next = cur;
  22.                     ae = ae.next;
  23.                 }
  24.             }
  25.             cur = cur.next;
  26.         }
  27.         //都是比x大的情况
  28.         if(bs == null){
  29.             return as;
  30.         }
  31.         be.next = as;
  32.         //最后都要置为null，不然可能会报错
  33.         if(as!=null){
  34.             ae.next = null;
  35.         }
  36.         return bs;
  37.     }
  38. }

Cabe señalar que si son mayores que x, es decir, bs = null, entonces as se devolverá directamente, y si as.next finalmente se establece en null

6. Estructura palíndromo de la lista enlazada OR36

Estructura palíndromo OR36 de lista enlazada

Esta es una pregunta de Niuke, porque tiene requisitos de complejidad de tiempo y complejidad de espacio, lo que significa que no se puede abrir una matriz adicional; de lo contrario, la complejidad del espacio no se superará y el recorrido normal tendrá una complejidad de O (n)

La idea es la siguiente: primero busque el nodo intermedio lento de la lista vinculada y luego invierta la parte desde el medio hasta el final. El nodo principal se recorre hacia atrás y el nodo lento también se realiza una comparación. los valores son diferentes, significa que no regresan a la estructura del texto.

Invertir la lista enlazada y encontrar el nodo intermedio se ha practicado antes

  1. public class PalindromeList {
  2.     public boolean chkPalindrome(ListNode head) {
  3.         if (head == null) {
  4.             return true;
  5.         }
  6.         //找到中间节点
  7.         ListNode fast = head;
  8.         ListNode slow = head;
  9.         while (fast != null && fast.next != null) {
  10.             fast = fast.next.next;
  11.             slow = slow.next;
  12.         }
  13.         //从slow开始到末尾反转
  14.         ListNode cur = slow.next;
  15.         while (cur != null) {
  16.             ListNode curn = cur.next;
  17.             cur.next = slow;
  18.             slow = cur;
  19.             cur = curn;
  20.         }
  21.         //判断回文
  22.         while (head != slow) {
  23.             if (head.val != slow.val) {
  24.                 return false;
  25.             }
  26.             //判断偶数节点
  27.             if (head.next == slow) {
  28.                 return true;
  29.             }
  30.             head = head.next;
  31.             slow = slow.next;
  32.         }
  33.         return true;
  34.     }
  35. }

Cabe señalar que también existe una diferencia en el juicio entre la lista vinculada de nodos impares y la lista vinculada de nodos pares.

Si el nodo par se mueve hacia arriba, provocará un bucle infinito, por lo que se necesita un juicio adicional para el nodo par.

7. Listas enlazadas intersecadas

160. Listas enlazadas intersecadas

La lista enlazada que se cruza es una transformación similar a "Y", como se muestra en la figura

La imagen de la siguiente pregunta también es muy clara.

Idea: porque ya sea que A sea corto o B sea corto, la diferencia entre ellos es la parte antes de la intersección. Solo necesita mover la lista enlazada larga por una diferencia, y luego los dos nodos de la lista enlazada retroceden al mismo tiempo. nodos idénticos deben cruzarse con el nodo de.

  1. public class Solution {
  2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  3.         ListNode pl = headA;
  4.         ListNode ps = headB;
  5.         int cnta = 0,cntb = 0;
  6.         //计算两个链表的长度
  7.         while(pl!=null){
  8.             pl = pl.next;
  9.             cnta++;
  10.         }
  11.         while(ps!=null){
  12.             ps = ps.next;
  13.             cntb++;
  14.         }
  15.         //如果链表b长，就更新pl,ps
  16.         int len = cnta - cntb;
  17.         //上面求长度时pl,ps都为空了，所以这里再重新指向
  18.         pl = headA;
  19.         ps = headB;
  20.         if(len < 0){
  21.             pl = headB;
  22.             ps = headA;
  23.             len = cntb - cnta;
  24.         }
  25.         //移动差值
  26.         while(len!=0){
  27.             pl = pl.next;
  28.             len--;
  29.         }
  30.         //找到相交节点
  31.         while(pl!=ps){
  32.             pl = pl.next;
  33.             ps = ps.next;
  34.         }
  35.         //链表不相交的情况
  36.         if(pl == null) return null;
  37.         return pl;
  38.     }
  39. }

Finalmente, debemos agregar la situación disjunta. Aunque podemos pasar esta pregunta sin agregarla, aún debemos agregarla por razones de rigor.

8. Lista circular enlazada

8.1 Determinar si hay un bucle

141. Lista circular enlazada

Cómo determinar si una lista vinculada tiene un ciclo:Todavía use el puntero de velocidad, al igual que dos personas corriendo en el patio de recreo, una persona corre rápido y la otra corre lentamente. Dado que el patio de recreo es un anillo, el rápido definitivamente puede superar al lento. , pero si no fuera por Tamaki, nunca podrían encontrarse, al igual que una diosa que no puedes atrapar por mucho que la persigas.

Pero hay otra situación, si es un anillo con dos nodos, y el puntero rápido definido da 3 pasos a la vez y el puntero lento da 1 paso a la vez, entonces nunca se encontrarán.

Por lo tanto, los punteros definidos deben juzgar cuántos pasos dan cada vez. Si uno da 2 pasos y el otro da 1 paso, definitivamente se encontrarán.

  1. public class Solution {
  2.     public boolean hasCycle(ListNode head) {
  3.         ListNode fast = head;
  4.         ListNode slow = head;
  5.         while(fast!=null&&fast.next!=null){
  6.             fast = fast.next.next;
  7.             slow = slow.next;
  8.             if(fast == slow) return true;
  9.         }
  10.         return false;
  11.     }
  12. }

8.2 Devolver el nodo en la entrada del anillo

142. Lista circular enlazada II

Esta vez necesitas averiguar el punto de entrada al anillo después de juzgar si es un anillo en la pregunta anterior. Puedes hacer el siguiente razonamiento.

  1. public class Solution {
  2.     public ListNode detectCycle(ListNode head) {
  3.         ListNode fast = head;
  4.         ListNode slow = head;
  5.         //判断环
  6.         while(fast!=null&&fast.next!=null){
  7.             fast = fast.next.next;
  8.             slow = slow.next;
  9.             if(fast == slow) break;
  10.         }
  11.         if(fast == null||fast.next == null) return null;
  12.         slow = head;
  13.         //寻找环
  14.         while(slow!=fast){
  15.             slow = slow.next;
  16.             fast = fast.next;
  17.         }
  18.         return slow;
  19.     }
  20. }

Lo que hay que añadir es:

Cuando el anillo es muy pequeño, el resultado final de la simplificación es el anterior, pero el código original aún está bien.

Perfil personal

Se ha dedicado a la investigación de tecnología durante más de treinta años, domina varios lenguajes como java, linux, javascript, php, css, etc., y ha realizado muchas contribuciones en el campo del código abierto. una estación de documentación para desarrolladores para compartir algunos problemas en el desarrollo de tecnología para referencia futura.

Mi informacion de contacto

Correo