Listas Simplesmente Encadeadas

tags: interview-training linked-list c++

Estrutura Básica:

struct ListNode {
  int val;
  ListNode* next;
  ListNode() : val(0), next(nullptr) {} 
  ListNode(int x) : val(x), next(nullptr) {}
};

Visualizando…

Vantagens:
Remover nó em O(1)

Desvantagens:
Acessar nó qualquer em O(n)

Operações

Obs: os códigos são apenas para aprendizado e não foram testados

Remover elemento:

// Remover Elemento
// Obs: para entrevista, não precisa se preocupar em desalocar 
// a memória do nó que vai ser removido

ListNode* removeElement (ListNode* head, int index) {
  ListNode* prev = nullptr;
  ListNode* current = head;

  if(head == nullptr) return head;

  while(index) {
    prev = current;
    current = current -> next;
    if(current == nullptr) return head;
    index--;
  }

  if(prev == nullptr) {
    head = head -> next;
  } else {
    prev -> next = current -> next;
  }

  return head;
}

Exercícios:
https://leetcode.com/problems/delete-node-in-a-linked-list/
https://leetcode.com/problems/remove-nth-node-from-end-of-list/

---

Inserir Elemento:

// Inserir elemento 

ListNode* insertElement (ListNode* head, int val, int index) {
  ListNode* prev = nullptr;
  ListNode* current = head;

  while(index) {
    prev = current;
    if(current == nullptr) break;
    current = current -> next;
    index--;
  }

  ListNode* newNode = new ListNode(val);

  if(prev == nullptr) {
    newNode -> next = head;
    head = newNode;
  } else {
    prev->next = newNode;
    newNode -> next = current;
  }

  return head;
}

---

Construir lista a partir de um vector:

// Construir uma lista encadeada a partir de um vector

ListNode* build (vector<int> v) {
  ListNode* prev = nullptr;
  ListNode* head = nullptr;

  for(int i = 0; i < v.size(); i++) {
    ListNode* newNode = new ListNode(v[i]);
    
    if(prev == nullptr) head = newNode;
    else prev->next = newNode;
    
    prev = newNode;
  }

  return head;
}

---

Deep copy:

// Fazer deep copy (memória precisa ser alocada, os novos
//  ponteiros não irão apontar para os mesmos endereços da lista de input)

ListNode* deepCopy (ListNode* head) {
  ListNode* prev = nullptr;
  ListNode* headCopy = nullptr;

  while(head != nullptr) {
    ListNode* copyNode = new ListNode(head -> val);

    if(prev == nullptr) headCopy = copyNode;
    else prev->next = copyNode;

    head = head -> next;
    prev = copyNode;
  }

  return headCopy;
}

---

Reverter Lista:

// Reverter lista

ListNode* reverse (ListNode* head) {
  if(head == nullptr) return head;

  ListNode* prev = nullptr;
  ListNode* next = nullptr;
  
  while(head != nullptr) {
    next = head -> next;
    head -> next = prev;
    prev = head;
    head = next;
  }
  
  return prev;
}

Exercícios:
https://leetcode.com/problems/reverse-linked-list/
https://leetcode.com/problems/reverse-nodes-in-k-group/

---

Printar lista:

// Printar lista encadeada

void print (ListNode* head) {
  while(head != nullptr) {
    cout << head -> val << " ";
    head = head -> next;
  }
  cout << endl;
}

Assuntos Extras

Detecção de ciclo:
Técnica do ponteiro rápido e lento (floyd's Tortoise and Hare), o ponteiro rápido irá andar de dois em dois passos, enquanto que o lento andará de um em um, se os dois se encontrarem, é porque existe um ciclo.

Complexidade: O(n)

Extra: Como encontrar o início do ciclo?

Exercícios:
https://leetcode.com/problems/linked-list-cycle/
https://leetcode.com/problems/linked-list-cycle-ii/

---

Lista com random pointer:

struct ListNode {
  int val;
  ListNode* next;
  ListNode* random;
  ListNode() : val(0), next(nullptr), random(nullptr) {} 
  ListNode(int x) : val(x), next(nullptr), random(nullptr) {}
};

Visualizando:

Como fazer deep copy?

Opção 1: usar um map <LinkedList*, LinkedList*> associando cada nó da lista original com sua cópia

Opção 2: criar uma lista encadeada em que os nós nas posições ímpares são os originais e nas posições pares são as cópias

Exercício:
https://leetcode.com/problems/copy-list-with-random-pointer/

---

MergeSort com lista encadeada:

Bem direto, bom para treinar, a parte que pode complicar é o merge de duas listas encadeadas, então segue uns exercícios para praticar justamente isso:
https://leetcode.com/problems/merge-two-sorted-lists/
https://leetcode.com/problems/merge-k-sorted-lists/

---

Questões ultra clássicas:

Somar dois números que estão na forma de lista encadeada:
Obs: atentar aos casos que precisa criar um novo nó
https://leetcode.com/problems/add-two-numbers/

Verificar se lista encadeada é um palíndromo:
Uma opção é reverter primeira metade da lista, andar na primera metade (revertida) e na segunda e verificar se os nós tem os mesmos valores
https://leetcode.com/problems/palindrome-linked-list/