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. ListNode cur = head.next;
  8. //head变为了末尾元素,指向null
  9. head.next = null;
  10. while(cur!=null){
  11. //curn为cur的next节点,便于往后移动
  12. ListNode curn = cur.next;
  13. cur.next = head;
  14. head = cur;
  15. //更新cur
  16. cur = curn;
  17. }
  18. return head;
  19. }
  20. }

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. while (fast.next != null) {
  19. fast = fast.next;
  20. slow = slow.next;
  21. }
  22. return slow.val;
  23. }
  24. }

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. while(list1!=null&&list2!=null){
  6. if(list1.val < list2.val){
  7. tmp.next = list1;
  8. list1 = list1.next;
  9. tmp = tmp.next;
  10. }else{
  11. tmp.next = list2;
  12. list2 = list2.next;
  13. tmp = tmp.next;
  14. }
  15. }
  16. //判断剩余的情况
  17. if(list1!=null){
  18. tmp.next = list1;
  19. }else if(list2!=null){
  20. tmp.next = list2;
  21. }
  22. return head.next;
  23. }
  24. }

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.