Compartilhamento de tecnologia

Perguntas selecionadas do teste de superfície de Likou e Niukelian

2024-07-12

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

💎 欢迎各位大佬互三：minha página inicial

1. Lista vinculada inversamente

206.Lista vinculada reversa

Pensando: Se você não abrir espaço adicional e apenas modificar a lista vinculada original, qual método deve ser usado?

Basta começar a partir do segundo elemento e realizar a inserção do cabeçote em sequência.

Depois é só modificar a referência e apontar o último elemento para null

  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. O nó intermediário da lista vinculada

876. Nó intermediário da lista vinculada

O primeiro método que vem à mente para esta questão é definitivamente definir um cnt, percorrer a lista vinculada uma vez, encontrar o número do meio e, em seguida, percorrer o valor de retorno. Este método é muito simples, mas e se você precisar percorrer o valor de retorno. lista vinculada apenas uma vez para encontrar o nó intermediário?

Aqui está uma nova ideia: use os ponteiros rápidos e lentos, começando pela cabeça. O ponteiro rápido move dois nós de cada vez, e o ponteiro lento move um nó de cada vez.

Então vamos implementá-lo:

  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. }

Isso seria mais eficiente?

3. Retorne o k-ésimo nó do último

Pergunta da entrevista 02.02.

A primeira coisa que vem à mente para esta questão é percorrê-la uma vez para obter o comprimento total e, em seguida, encontrar o k-ésimo nó do último. No entanto, com base na questão anterior, você pode pensar em outro método: De forma similar,Usando os ponteiros rápido e lento, deixe os nós k-1 irem rápido primeiro e, em seguida, vá devagar e rápido ao mesmo tempo. Quando o próximo de rápido for nulo, significa que rápido atingiu o último nó e lento neste momento. é o k-ésimo nó da parte inferior.

Esta questão indica que a entrada k é legal, portanto, nenhum julgamento adicional é necessário. Como julgar se k é ilegal, e é necessário que o comprimento da lista vinculada não possa ser encontrado diretamente, portanto, é necessário julgar lentamente enquanto caminha.

  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. Mesclar listas vinculadas

21. Mesclar duas listas vinculadas ordenadas

Ideia:Você só precisa definir um novo nó newH e, em seguida, comparar o valor de headA e headB. Para finalmente encontrar o nó principal da lista vinculada mesclada, você também precisa definir a tmp = newH e, em seguida, quem tiver o menor. tmp.next apontará para ele.

  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. Divisão de lista vinculada

Divisão da lista vinculada CM11

Esta é uma pergunta de entrevista sobre Niuke. O significado da pergunta é dividir a lista vinculada. O lado esquerdo de x é menor que x e o lado direito é maior que x.

Idéia: definir um novo nó cur para percorrer a lista vinculada original (para evitar que a lista vinculada original seja alterada), colocar tudo maior que x em uma lista vinculada, colocar tudo menor que x em uma lista vinculada e, finalmente, conectar os dois listas vinculadas.

  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. }

Deve-se notar que se eles forem maiores que x, ou seja, bs = null, então as será retornado diretamente, e se as.next for finalmente definido como null

6. Estrutura do palíndromo da lista vinculada OR36

Estrutura palíndromo OR36 da lista vinculada

Esta é uma pergunta de Niuke, porque possui requisitos de complexidade de tempo e complexidade de espaço, o que significa que você não pode abrir um array adicional, caso contrário a complexidade do espaço não será superada e a travessia normal terá uma complexidade de O(n)

A ideia é a seguinte: primeiro encontre o nó intermediário lento da lista vinculada e, em seguida, inverta a parte do meio para o final. O nó principal é percorrido para trás e o nó lento também é percorrido para trás. os valores são diferentes, significa que não estão retornando estrutura de texto.

Reverter a lista vinculada e encontrar o nó intermediário já foi praticado 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. }

Deve-se notar que também há uma diferença no julgamento da lista vinculada de nós ímpares e da lista vinculada de nós pares.

Se o nó par for movido para o topo, isso causará um loop infinito, portanto, é necessário um julgamento adicional para o nó par.

7. Listas vinculadas cruzadas

160. Listas vinculadas cruzadas

A lista vinculada que se cruza é uma transformação semelhante a "Y", conforme mostrado na figura

A imagem da pergunta abaixo também é muito clara.

Idéia: porque se A é curto ou B é curto, a diferença entre eles é a parte antes da interseção. Você só precisa mover a lista vinculada longa por uma diferença e, em seguida, os dois nós da lista vinculada se movem para trás ao mesmo tempo. nós idênticos devem cruzar o nó 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, precisamos de adicionar a situação disjunta Embora possamos passar esta questão sem adicioná-la, ainda precisamos de adicioná-la por uma questão de rigor.

8. Lista vinculada circular

8.1 Determine se existe um loop

141. Lista circular vinculada

Como determinar se uma lista vinculada possui um ciclo:Ainda use o ponteiro de velocidade, assim como duas pessoas correndo no playground, uma pessoa corre rápido e a outra corre devagar. Como o playground é um ringue, o rápido pode definitivamente ultrapassar o lento. , mas se não fosse por Tamaki, eles nunca seriam capazes de se encontrar, assim como uma deusa que você não pode pegar, não importa o quanto você persiga.

Mas há outra situação: se for um anel com dois nós, e o ponteiro rápido definido der 3 passos de cada vez e o ponteiro lento der 1 passo de cada vez, então eles nunca se encontrarão.

Portanto, os ponteiros definidos precisam julgar quantos passos eles dão de cada vez. Se um dá 2 passos e o outro dá 1 passo, eles definitivamente se encontrarão.

  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 Retornar o nó na entrada do anel

142. Lista Circular Vinculada II

Desta vez, você precisa descobrir o ponto de entrada no anel depois de julgar se é um anel na questão anterior. Você pode fazer o seguinte raciocínio.

  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. }

O que precisa ser adicionado é:

Quando o anel é muito pequeno, o resultado final da simplificação torna-se o acima, mas o código original ainda está bom.

Perfil pessoal

Ele se dedica à pesquisa de tecnologia há mais de 30 anos e é proficiente em diversas linguagens como java, linux, javascript, php, css, etc. estação de documentação do desenvolvedor para compartilhar alguns problemas no desenvolvimento de tecnologia para referência futura.

minhas informações de contato

Correspondência