Обмен технологиями

Избранные вопросы по испытаниям поверхности Ликоу, Нюкеляна

2024-07-12

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

💎 欢迎各位大佬互三：моя домашняя страница

1. Обратно связанный список

206.Обратно связанный список

Подумайте: если вы не открываете дополнительное пространство, а изменяете только исходный связанный список, какой метод следует использовать?

Просто начните со второго элемента и последовательно выполняйте вставку головки.

Затем просто измените ссылку и укажите последнему элементу значение 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. Средний узел связанного списка.

876. Промежуточный узел связного списка.

Первый метод, который приходит на ум при ответе на этот вопрос, — это определить cnt, один раз пройти по связанному списку, затем найти среднее число и затем пройти по возвращаемому значению. Этот метод очень прост, но что, если вам нужно пройти по всему списку? связанный список только один раз, чтобы найти промежуточный узел?

Вот новая идея: используйте быстрый и медленный указатели, начиная с головы. Быстрый указатель каждый раз перемещает два узла, а медленный — один узел. Достигается ли это конечной цели?

Тогда давайте реализуем это:

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

Будет ли это более эффективно?

3. Вернуть k-й узел из последнего

Вопрос на собеседовании 02.02. Вернуть k-й узел из последнего.

Первое, что приходит на ум по этому вопросу, — пройти его один раз, чтобы получить общую длину, а затем найти k-й узел из последнего. Однако на основе предыдущего вопроса можно придумать другой метод: Сходным образом,Используя указатели «быстрый» и «медленный», сначала пропустите k-1 узлов быстро, а затем одновременно пройдите медленный и быстрый. Когда следующий из «быстрых» равен нулю, это означает, что «быстрый» достиг последнего узла, а «медленный» в это время. — k-й узел снизу.

Этот вопрос указывает на то, что ввод k является допустимым, поэтому не требуется никаких дополнительных суждений. Как определить, является ли k незаконным, и требуется, чтобы длина связанного списка не могла быть найдена напрямую, поэтому медленно нужно оценивать во время ходьбы.

  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. Объединить связанные списки

21. Объединить два упорядоченных связанных списка.

Идея:Вам нужно всего лишь определить новый узел newH, а затем сравнить значения headA и headB. Чтобы наконец найти головной узел объединенного связанного списка, вам также необходимо определить tmp = newH, а затем тот, у которого меньшее значение. tmp.next укажет на это.

  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. Разделение связанного списка

Разделение связанного списка CM11

Это вопрос для собеседования на Niuke. Смысл вопроса состоит в том, чтобы разделить связанный список. Левая часть x меньше x, а правая часть больше x. Исходный порядок изменить нельзя.

Идея: определить новый узел Cur для обхода исходного связанного списка (чтобы предотвратить изменение исходного связанного списка), поместить все, что больше x, в связанный список, поместить все, что меньше x, в связанный список и, наконец, соединить их. связанные списки.

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

Следует отметить, что если они больше x, то есть bs = null, то as будет возвращено напрямую, а если as.next окончательно будет установлен в значение null

6. Палиндромная структура связанного списка OR36.

Структура палиндрома OR36 связанного списка

Это вопрос от Niuke, потому что у него есть требования к временной и пространственной сложности, а это значит, что вы не можете открыть дополнительный массив, иначе пространственная сложность не будет преодолена, и нормальный обход будет иметь сложность O(n)

Идея такая: сначала найти средний узел медленного связанного списка, а затем перевернуть часть от середины к концу. Головной узел проходится назад, а медленный узел также проходится назад. значения разные, значит не возвращают текстовую структуру.

Обращение связанного списка и поиск промежуточного узла практиковались и раньше.

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

Следует отметить, что существует также разница в оценке связанного списка узлов с нечетными номерами и связанного списка узлов с четными номерами.

Если узел с четным номером переместить наверх, это вызовет бесконечный цикл, поэтому для узла с четным номером потребуется дополнительная оценка.

7. Пересекающиеся связанные списки

160. Пересекающиеся связанные списки

Пересекающийся связанный список — это преобразование, аналогичное «Y», как показано на рисунке.

Картина в вопросе ниже также очень ясна.

Идея: потому что независимо от того, является ли A коротким или B, разница между ними - это часть до пересечения. Вам нужно всего лишь переместить длинный связанный список на разницу, а затем два узла связанного списка одновременно перемещаются назад. одинаковые узлы должны пересекать узел.

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

Наконец, нам нужно добавить непересекающуюся ситуацию. Хотя мы можем пропустить этот вопрос, не добавляя его, нам все равно придется добавить его для строгости.

8. Круговой связанный список

8.1 Определите, есть ли петля

141. Круговой связанный список

Как определить, есть ли в связанном списке цикл:По-прежнему используйте указатель скорости, так же, как два человека бегут по детской площадке: один бежит быстро, а другой бежит медленно. Поскольку игровая площадка представляет собой кольцо, быстрый человек определенно может превзойти медленного. В этот раз они встретились. , но если бы не Тамаки, они бы никогда не смогли встретиться, как богиня, которую не поймаешь, как бы сильно ни гонялся.

Но есть и другая ситуация. Если это кольцо с двумя узлами, и определенный быстрый указатель делает 3 шага за раз, а медленный указатель делает 1 шаг за раз, то они никогда не встретятся.

Поэтому определившимся указателям необходимо каждый раз судить, сколько шагов они сделают. Если один сделает 2 шага, а другой — 1 шаг, они обязательно встретятся.

  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 Возврат узла на входе в кольцо

142. Циркулярный связанный список II.

На этот раз вам нужно узнать точку входа в кольцо, рассудив, является ли это кольцом в предыдущем вопросе. Вы можете сделать следующие рассуждения.

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

Что необходимо добавить, так это:

Когда кольцо очень маленькое, окончательный результат упрощения будет таким, как указано выше, но исходный код по-прежнему в порядке.

Личный профиль

Он посвятил себя исследованию технологий более 30 лет и владеет различными языками, такими как Java, Linux, Javascript, php, css и т. д. Он внес большой вклад в область открытого исходного кода. Станция документации для разработчиков, где можно поделиться некоторыми проблемами в разработке технологий для дальнейшего использования. Все ознакомьтесь.

моя контактная информация

Почта