Partage de technologie

Questions sélectionnées du test de surface Likou, niukélien

2024-07-12

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

💎 欢迎各位大佬互三：ma page d'accueil

1. Liste chaînée inversée

206.Liste chaînée inversée

Réflexion : si vous n'ouvrez pas d'espace supplémentaire et modifiez uniquement la liste chaînée d'origine, quelle méthode devez-vous utiliser ?

Commencez simplement par le deuxième élément et effectuez l’insertion de la tête dans l’ordre.

Ensuite, modifiez simplement la référence et pointez le dernier élément sur 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. Le nœud central de la liste chaînée

876. Nœud intermédiaire de liste chaînée

La première méthode qui me vient à l'esprit pour cette question est certainement de définir un cnt, de parcourir la liste chaînée une fois, puis de trouver le nombre du milieu, puis de parcourir la valeur de retour. Cette méthode est très simple, mais que se passe-t-il si vous devez parcourir le nombre du milieu. liste chaînée une seule fois pour trouver le nœud intermédiaire ?

Voici une nouvelle idée : utilisez les pointeurs rapides et lents, en commençant par la tête. Le pointeur rapide déplace deux nœuds à chaque fois, et le pointeur lent déplace un nœud à chaque fois. Cela atteint-il l'objectif ultime ?

Alors implémentons-le :

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

Serait-ce plus efficace ?

3. Renvoyez le k-ème nœud du dernier

Question d'entretien 02.02. Renvoyez le k-ème nœud du dernier.

La première chose qui vient à l’esprit pour cette question est de la parcourir une fois pour obtenir la longueur totale, puis de trouver le k-ième nœud du dernier. Cependant, sur la base de la question précédente, vous pouvez penser à une autre méthode : De la même manière,À l'aide des pointeurs rapide et lent, relâchez d'abord les nœuds k-1, puis lent et rapide en même temps. Lorsque le prochain de rapide est nul, cela signifie que rapide a atteint le dernier nœud et lent à ce moment-là. est le k-ème nœud à partir du bas.

Cette question indique que l'entrée k est légale, donc aucun jugement supplémentaire n'est nécessaire. Comment juger si k est illégal, et il est nécessaire que la longueur de la liste chaînée ne puisse pas être trouvée directement, donc la lenteur doit être jugée en marchant.

  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. Fusionner les listes chaînées

21. Fusionner deux listes chaînées ordonnées

Idée:Il vous suffit de définir un nouveau nœud newH, puis de comparer les valeurs de headA et headB. Afin de trouver enfin le nœud principal de la liste chaînée fusionnée, vous devez également définir un tmp = newH, puis celui qui a le plus petit. tmp.next le pointera.

  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. Division de la liste chaînée

Division de la liste chaînée CM11

Il s'agit d'une question d'entretien sur Niuke. Le sens de la question est de diviser la liste chaînée. Le côté gauche de x est plus petit que x et le côté droit est plus grand que x.

Idée : définir un nouveau nœud cur pour parcourir la liste chaînée d'origine (pour éviter que la liste chaînée d'origine ne soit modifiée), mettre tout ce qui est plus grand que x dans une liste chaînée, mettre tout ce qui est plus petit que x dans une liste chaînée, et enfin connecter les deux listes chaînées.

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

Il convient de noter que s'ils sont supérieurs à x, c'est-à-dire bs = null, alors as sera renvoyé directement, et si as.next est finalement défini sur null

6. Structure palindrome de la liste chaînée OR36

Structure palindrome OR36 de la liste chaînée

C'est une question de Niuke, car elle a des exigences de complexité temporelle et spatiale, ce qui signifie que vous ne pouvez pas ouvrir un tableau supplémentaire, sinon la complexité spatiale ne sera pas surmontée et le parcours normal aura une complexité de O(n)

L'idée est la suivante : recherchez d'abord le nœud central lent de la liste chaînée, puis inversez la partie du milieu vers la fin. Le nœud principal est parcouru vers l'arrière, et le nœud lent est également parcouru vers l'arrière. les valeurs sont différentes, cela signifie qu'elles ne renvoient pas la structure du texte.

Inverser la liste chaînée et trouver le nœud intermédiaire ont déjà été pratiqués

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

Il convient de noter qu'il existe également une différence dans le jugement de la liste chaînée de nœuds impairs et de la liste chaînée de nœuds pairs.

Si le nœud pair est déplacé vers le haut, cela provoquera une boucle infinie, un jugement supplémentaire est donc nécessaire pour le nœud pair.

7. Listes chaînées croisées

160. Listes chaînées croisées

La liste chaînée qui se croise est une transformation similaire à "Y", comme le montre la figure

L’image de la question ci-dessous est également très claire.

Idée : Parce que si A est court ou B est court, la différence entre eux est la partie avant l'intersection. Il vous suffit de déplacer la longue liste chaînée d'une différence, puis les deux nœuds de la liste chaînée reculent en même temps. les nœuds identiques doivent croiser le nœud 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. }

Enfin, nous devons ajouter la situation disjointe. Bien que nous puissions passer cette question sans l'ajouter, nous devons quand même l'ajouter par souci de rigueur.

8. Liste chaînée circulaire

8.1 Déterminer s'il y a une boucle

141. Liste chaînée circulaire

Comment déterminer si une liste chaînée a un cycle :Utilisez toujours le pointeur de vitesse, tout comme deux personnes qui courent sur le terrain de jeu, une personne court vite et l'autre court lentement. Puisque le terrain de jeu est un anneau, le plus rapide peut certainement dépasser le lent. , mais sans Tamaki, ils ne pourraient jamais se rencontrer, tout comme une déesse que vous ne pouvez pas attraper, peu importe à quel point vous poursuivez.

Mais il existe une autre situation. S'il s'agit d'un anneau avec deux nœuds et que le pointeur rapide défini fait 3 pas à la fois et que le pointeur lent fait 1 pas à la fois, alors ils ne se rencontreront jamais.

Par conséquent, les pointeurs définis doivent juger du nombre de pas qu'ils font à chaque fois. Si l'un fait 2 pas et l'autre 1 pas, ils se rencontreront certainement.

  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 Restituer le nœud à l'entrée du ring

142. Liste circulaire chaînée II

Cette fois, vous devez connaître le point d’entrée dans l’anneau après avoir jugé s’il s’agit d’un anneau à la question précédente. Vous pouvez faire le raisonnement suivant.

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

Ce qu'il faut ajouter c'est :

Lorsque l'anneau est très petit, le résultat final de la simplification devient celui ci-dessus, mais le code original reste correct.

Profil personnel

Il se consacre à la recherche technologique depuis plus de trente ans, maîtrise divers langages tels que java, linux, javascript, php, css, etc., et a apporté de nombreuses contributions dans le domaine de l'open source. une station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.

mes coordonnées

Mail