minhas informações de contato
Correspondência[email protected]
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
💎 欢迎各位大佬互三:minha página inicial
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
- class Solution {
- public ListNode reverseList(ListNode head) {
- //head为null,直接返回
- if(head == null){
- return head;
- }
-
- ListNode cur = head.next;
- //head变为了末尾元素,指向null
- head.next = null;
- while(cur!=null){
- //curn为cur的next节点,便于往后移动
- ListNode curn = cur.next;
- cur.next = head;
- head = cur;
- //更新cur
- cur = curn;
- }
- return head;
- }
- }
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:
- class Solution {
- public ListNode middleNode(ListNode head) {
- if(head == null){
- return null;
- }
- ListNode fast = head;
- ListNode slow = head;
- while(fast!= null&&fast.next!= null){
- fast = fast.next.next;
- slow = slow.next;
- }
- return slow;
- }
- }
Isso seria mais eficiente?
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.
- class Solution {
- public int kthToLast(ListNode head, int k) {
- if (head == null) {
- return -1;
- }
- ListNode fast = head;
- ListNode slow = head;
- int cnt = 0;
- while (cnt != k - 1) {
- //判断k的合法性,虽然本题不用判断
- fast = fast.next;
- if(fast == null){
- return;
- }
- cnt++;
- }
- //slow和fast同时移动
-
- while (fast.next != null) {
- fast = fast.next;
- slow = slow.next;
- }
- return slow.val;
- }
- }
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.
- class Solution {
- public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
- ListNode head = new ListNode();
- ListNode tmp = head;
-
- while(list1!=null&&list2!=null){
- if(list1.val < list2.val){
- tmp.next = list1;
- list1 = list1.next;
- tmp = tmp.next;
- }else{
- tmp.next = list2;
- list2 = list2.next;
- tmp = tmp.next;
- }
- }
- //判断剩余的情况
- if(list1!=null){
- tmp.next = list1;
- }else if(list2!=null){
- tmp.next = list2;
- }
- return head.next;
- }
- }
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.
- public class Partition {
- public ListNode partition(ListNode pHead, int x) {
- ListNode bs = null;
- ListNode be = null;
- ListNode as = null;
- ListNode ae = null;
- ListNode cur = pHead;
- while (cur != null) {
- if (cur.val < x) {
- //处理刚开始为null的情况
- if (bs == null) {
- bs = be = cur;
- }else{
- be.next = cur;
- be = be.next;
- }
- }else{
- if(as == null){
- as = ae = cur;
- }else{
- ae.next = cur;
- ae = ae.next;
- }
- }
- cur = cur.next;
- }
- //都是比x大的情况
- if(bs == null){
- return as;
- }
- be.next = as;
- //最后都要置为null,不然可能会报错
- if(as!=null){
- ae.next = null;
- }
- return bs;
- }
- }
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
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
- public class PalindromeList {
- public boolean chkPalindrome(ListNode head) {
- if (head == null) {
- return true;
- }
- //找到中间节点
- ListNode fast = head;
- ListNode slow = head;
- while (fast != null && fast.next != null) {
- fast = fast.next.next;
- slow = slow.next;
- }
- //从slow开始到末尾反转
- ListNode cur = slow.next;
- while (cur != null) {
- ListNode curn = cur.next;
- cur.next = slow;
- slow = cur;
- cur = curn;
- }
- //判断回文
- while (head != slow) {
- if (head.val != slow.val) {
- return false;
- }
- //判断偶数节点
- if (head.next == slow) {
- return true;
- }
- head = head.next;
- slow = slow.next;
- }
- return true;
- }
- }
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.
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.
- public class Solution {
- public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
- ListNode pl = headA;
- ListNode ps = headB;
- int cnta = 0,cntb = 0;
- //计算两个链表的长度
- while(pl!=null){
- pl = pl.next;
- cnta++;
- }
- while(ps!=null){
- ps = ps.next;
- cntb++;
- }
- //如果链表b长,就更新pl,ps
- int len = cnta - cntb;
- //上面求长度时pl,ps都为空了,所以这里再重新指向
- pl = headA;
- ps = headB;
- if(len < 0){
- pl = headB;
- ps = headA;
- len = cntb - cnta;
- }
- //移动差值
- while(len!=0){
- pl = pl.next;
- len--;
- }
- //找到相交节点
- while(pl!=ps){
- pl = pl.next;
- ps = ps.next;
- }
- //链表不相交的情况
- if(pl == null) return null;
- return pl;
- }
- }
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.
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.
- public class Solution {
- public boolean hasCycle(ListNode head) {
- ListNode fast = head;
- ListNode slow = head;
- while(fast!=null&&fast.next!=null){
- fast = fast.next.next;
- slow = slow.next;
- if(fast == slow) return true;
- }
- return false;
- }
- }
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.
- public class Solution {
- public ListNode detectCycle(ListNode head) {
- ListNode fast = head;
- ListNode slow = head;
- //判断环
- while(fast!=null&&fast.next!=null){
- fast = fast.next.next;
- slow = slow.next;
- if(fast == slow) break;
- }
- if(fast == null||fast.next == null) return null;
- slow = head;
- //寻找环
- while(slow!=fast){
- slow = slow.next;
- fast = fast.next;
- }
- return slow;
- }
- }
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.