Como ler um para trás lista individualmente ligados?
https://stackoverflow.com/questions/1116720
-
12-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Um método que eu posso pensar é para inverter a lista e, em seguida, lê-lo.
Mas isso envolve a alteração da lista que é ruim.
Ou eu posso fazer uma cópia da lista e, em seguida, revertê-la, mas isso usa memória adicional O (n).
Existe algum método melhor que não usa memória extra e não modificar a lista e é executado em O (n)
código lista inversa ligada é algo como isto em c #
Void Reverse (Node head)
{
Node prev= null;
Node current = head;
Node nextNode = null;
while (current!=null)
{
nextNode = current.Next;
current.Next = prev;
prev=current;
current = nextNode;
}
head = prev;
}
solução recursiva é
void ReadBackWard (Node n)
{
if (n==null)
return;
else
ReadBackward(n.Next);
Console.WriteLine(n.Data);
}
Solução
Para usar O memória (n) e O (n) o desempenho, criar uma pilha; empurrar tudo em como você iterate na direção para a frente, em seguida, pop tudo fora, produzindo os resultados.
Para usar desempenho (n ^ 2) O (mas O (1) de memória extra), lê-lo para a frente a cada vez, até o nó antes da última vez que você tem que.
Exemplo:
IEnumerable<T> Reverse (Node head) {
Stack<Node> nodes = new Stack<Node>();
while(head != null) {
nodes.Push(head);
head = head.Next;
}
while(nodes.Count > 0) {
yield return nodes.Pop().Value;
}
}
Outras dicas
Uma das características de uma lista individualmente ligada é que ele é, de fato, vinculada isoladamente. É uma rua de sentido único, e não há nenhuma maneira de superar a menos que você transformá-lo em algo mais (como um invertido lista isoladamente ligada, uma pilha, uma lista duplamente vinculada ...). É preciso ser fiel à natureza das coisas.
Como foi apontado anteriormente; se você precisa percorrer uma lista para os dois lados; você precisa ter uma lista duplamente vinculada. Essa é a natureza de uma lista duplamente ligada, ele vai nos dois sentidos.
Realmente você deve estar usando uma lista duplamente vinculada.
Se isto não for possível, eu acho que sua melhor opção será a de construir uma cópia da lista que foi revertida.
Outras opções, como depender de recursão (copiando de forma eficaz a lista para a pilha) poderia causar-lhe a correr para fora do espaço de pilha se a lista é muito longa.
Se você curta de memória que você pode lista, iterate reversa sobre ele e revertê-la novamente. Alternativamente, você pode fazer uma pilha de ponteiros para nós (ou o que é como um ponteiro em C #).
void reverse_print(node *head)
{
node *newHead = NULL, *cur = head;
if(!head) return;
// Reverse the link list O(n) time O(1) space
while(cur){
head = head->next;
cur->next = newHead;
newHead = cur;
cur = head;
}
// Print the list O(n) time O(1) space
cur = newHead;
while(cur) {
printf(" %d", cur->val);
cur = cur->next;
}
// Reverse the link list again O(n) time O(1) space
cur = newHead;
while(cur){
newHead = newHead->next;
cur->next = head;
head = cur;
cur = newHead;
}
// Total complexity O(n) time O(1) space
}
Há uma terceira solução, desta vez usando a memória O(log(n)) e tempo O(n log(n)), ocupando assim o meio-termo entre as duas soluções em resposta de Marc.
É efetivamente uma descida reverso na ordem de uma árvore binária [O(log(n))], exceto em cada passo que você precisa para encontrar o topo da árvore [O(n)]:
- Split a lista em dois
- Recurse para a segunda metade da lista
- Imprima o valor no ponto médio
- Recurse na primeira metade
Aqui está a solução em Python (eu não sei C #):
def findMidpoint(head, tail):
pos, mid = head, head
while pos is not tail and pos.next is not tail:
pos, mid = pos.next.next, mid.next
return mid
def printReversed(head, tail=None):
if head is not tail:
mid = findMidpoint(head, tail)
printReversed(mid.next, tail)
print mid.value,
printReversed(head, mid)
Esta poderia ser reformulada usando iteração em vez de recursão, mas ao custo de clareza.
Por exemplo, para uma lista de um milhão de entrada, as três soluções assumir a ordem de:
Solution Memory Performance ========================================= Marc #1 4MB 1 million operations Mine 80B 20 million operations Marc #2 4B 1 trillion operations
Assumindo que a sua lista de implementos individualmente ligados IEnumerable
var backwards = singlyLinkedList.Reverse();
Você vai precisar adicionar uma directiva using System.Linq; no topo do arquivo de código para usar métodos de extensão do LINQ.
Uma variação de criar uma pilha e empurrando todos os elementos na pilha é usar recursão (e o sistema é construído em pilha), isso provavelmente não é o caminho a percorrer com o código de produção, mas serve como um melhor (IMHO) entrevista responder pelos seguintes motivos:
- Isso mostra que você grok recursão
- É menos código e parece mais elegante
- Um entrevistador ingênuo pode não perceber que há uma sobrecarga de espaço (se este for o caso, você pode querer considerar se você quer trabalhar lá).
Bem, a solução ingênua seria manter o controle de qual nó você está atualmente em, em seguida, iterate desde o início até encontrar esse nó, sempre salvando o nó que você acabou de sair. Em seguida, cada vez que você encontrar o nó que está atualmente em, você produz o nó que você acabou de sair, senão esse nó como aquele que está atualmente em, em seguida, re-iterate desde o início.
Isto de ser claro terrivelmente ruim em termos de performance.
Estou certeza que algumas pessoas mais inteligentes têm uma solução melhor.
Pseudo-código (com erros mesmo):
current node = nothing
while current node is not first node
node = start
while node is not current node
previous node = node
node = next node
produce previous node
set current node to previous node
Esta é confuso, mas funciona:
class SinglyLinkedList {
SinglyLinkedList next;
int pos;
SinglyLinkedList(int pos) {
this.pos = pos;
}
SinglyLinkedList previous(SinglyLinkedList startNode) {
if (startNode == this) return null;
if (startNode.next == this) return startNode;
else return previous(startNode.next);
}
static int count = 0;
static SinglyLinkedList list;
static SinglyLinkedList head;
static SinglyLinkedList tail;
public static void main (String [] args) {
init();
System.out.println("Head: " + head.pos);
System.out.println("Tail: " + tail.pos);
list = head;
System.out.print("List forwards: ");
while (list != null) {
System.out.print(list.pos + ",");
list = list.next;
}
list = tail;
System.out.print("\nList backwards: ");
while (list.previous(head) != null) {
System.out.print(list.pos + ",");
list = list.previous(head);
}
}
static void init() {
list = new SinglyLinkedList(0);
head = list;
while (count < 100) {
list.next = new SinglyLinkedList(++count);
list = list.next;
}
tail = list;
}
}
Se no programa explícita Stack, criamos uma pilha apenas para os dados de cada nó (em vez de criar a pilha de tipo <Node>, criamos Pilha de tipo <T>) não seria ainda melhor? Porque nós não precisamos para armazenar qualquer outra informação do Nó então.
IEnumerable<T> Reverse (Node<T> head) {
Stack<T> nodes = new Stack<T>();
while(head != null) {
nodes.Push(head.data);
head = head.Next;
}
while(nodes.Count > 0) {
yield return nodes.Pop();
}
}
Você pode lê-lo em O (n ^ 2) - cada vez ir para o último nó de ler e imprimir o anterior
O que há de errado com:
public void printBackwards(LinkedList sl){
ListIterator<Element> litr = sl.listIterator(sl.size());
Element temp;
while(litr.previousIndex() >= 0){
temp = litr.previous();
System.out.println(temp);
}
}
O (n) o desempenho, O (1) de memória e simples como Do-re-mi!
