Partir Lista ligada a meio

[mundo]

Bom dia, estou com duvidas a resolver um exercicio aqui de exame.

O enunciado é o seguinte:

Defina uma função break_list que parta uma lista ligada em dois segmentos de igual comprimento, devolvendo o endereço da lista correspondente ao segundo. Se a lista inicial tiver comprimento ímpar, o segundo segmento terá a mais um elemento do que o primeiro. Por exemplo, se a lista original tiver

os elementos 1,2,3,4,5,6,7, após a execução da função, a lista passa a ter apenas os valores 1,2,3 e o resultado da função deverá ser a lista com os elementos 4,5,6,7.

A função a definir só terá que produzir resultados válidos para listas de comprimento superior ou igual a 2.

Certifique-se que a solução apresentada executa em tempo linear no tamanho da lista e que não aloca memória adicional.

O codigo que eu tenho, e nao esta a funcionar bem, penso eu, é este:

typedef struct lnode {
int info;
struct lnode *next;
} Lnode, *List;

int comp(List l){
int i;

if(l == NULL) return 0;

while(l->next != NULL){
	i++;
}
return i;
}

List break_list(List l){
List aux, aux2;
int i, j, tam;

tam = comp(l);

if(l == NULL || comp(l) < 2) return;

if(comp(l)%2 != 0){

	for(i=0;i<(tam/2)-1 ; i++){
		aux->info = l->info;
		if(l->next == NULL){
			return NULL;
		}
		aux->next = l->next;
	}

	for(j = (tam/2); j < tam ; j++){
		aux2->info = l->info;
		if(l->next == NULL){
			return NULL;
		}
		aux2->next = l->next;
	}


}
else{

	for(i=0;i<(tam/2) ; i++){
		aux->info = l->info;

		if(l->next == NULL){
			aux->next = NULL;
		}
		aux->next = l->next;
	}

	for(j = (tam/2); j<tam ; j++){
		aux2->info = l->info;

		if(l->next == NULL){
			aux2->next = NULL;
		}
		aux2->next = l->next;
	}

}
return aux2;
}

[pmg]

Xiii ... não precisas de nada disso.

Repara que se arranjares dois ponteiros para percorrer a lista em que um percorre devagarinho e outro percorre depressa (de 2 em 2), quando o ponteiro rápido chegar ao fim, o ponteiro lento está a meio 🙂

Precisas de ter atenção a erros "off by one", mas basicamente é isto.

Edited February 1, 2013 at 12:28 PM by pmg

[mundo]

Mas ao fazer isso, caso seja impar a primeira parte não vai ter mais um que a segunda?

"Precisas de ter atenção a erros "off by one", mas basicamente é isto." É com isto que queres dizer isso?

Se for, tenho que depois passar manualmente o elemento a mais para a segunda parte certo?

[pmg]

Não, não, não. Não passas nada de lado nenhum para outro lado: fica tudo exactamente onde está.

Só precisas de alterar um único link: o link do último elemento da primeira metade da lista.

Por exemplo, para a lista {1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7} vais ao "3->next" e metes a NULL e devolves o valor que lá estava antes.

[mundo]

Com 2 ponteiros para percorrer, queres dizer 2 Lists's auxiliares? ou 2 inteiros i e j?

[HappyHippyHippo]

nem um nem outro

Lnode * l1 = NULL, * l2 = NULL; // dois iteradores de nós

Edited February 1, 2013 at 03:03 PM by HappyHippyHippo

[mundo]

nem um nem outro

Lnode * l1 = NULL, * l2 = NULL; // dois iteradores de nós

isso não é equivalente a ter?

List l1 = NULL, l2 = NULL;

[HappyHippyHippo]

sim é, em termos de significado é o mesmo

no entanto, o que apresentei lesse como dois ponteiros para nós de uma lista e o que apresentaste lesse como duas listas distintas.

o que escrevi era uma dica de como chegares à solução

[mundo]

Se for asneira peço, mas digam-me se assim está correcto

List break_list(List l){

   Lnode *l1 = NULL, *l2 = NULL;

   for(l1 = l; l1 != NULL; l1 = l1->next){
    for(l2 = l; l2 != NULL; l2 = l2->next + 2){

	    l2->info = l->info;
	    if(l2->next == NULL){
		    l1->next = NULL;
	    }
    }
   }
   return l2;
}

[HappyHippyHippo]

nop ... está errado

volta a ler o primeiro post do @pmg porque estás muito longe do pretendido

[mundo]

Não estou mesmo a conseguir implementar isto.

Deixa-me ver se percebi, a estrategia que o pmg referiu, seria de ter por exemplo, um while em que cada iteraçao incrementa 2, e dentro desse while 1 ciclo for para percorrer o que ira andar mais devagar, assim que o while parar, coloco o ponteiro->next do que anda devagar a apontar para nulo, e retorno o ponteiro rapido?

[HappyHippyHippo]

não

ele nunca referiu um ciclo dentro de um ciclo

o que ele disse foi um ciclo só em que os ponteiros "andam a velocidades diferentes"

[pmg]

Imagina a lista {1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8};

arranja dois ponteiros (lento e rapido) e mete-os a apontar para o 1

avanca o ponteiro lento 1 elemento e o rapido 2 elementos (o lento aponta para 2; o rapido aponta para 3)

avanca o ponteiro lento 1 elemento e o rapido 2 elementos (o lento aponta para 3; o rapido aponta para 5)

avanca o ponteiro lento 1 elemento e o rapido 2 elementos (o lento aponta para 4; o rapido aponta para 7)

avanca o ponteiro lento 1 elemento e o rapido 2 elementos (o lento aponta para 5; o rapido aponta para NULL)

Pronto!

O ponteiro lento aponta para o elemento que deve ser o primeiro da metade "nova" da lista (nesta situacao -- tens de verificar se acontece assim em todas as situacoes)

em codigo seria qualquer coisa assim

while (rapido != NULL) {
 lento = lento->next;
 rapido = rapido->next->next;
}

MAS ATENCAO QUE O CODIGO ESTA MUITO INCOMPLETO! Tens que acertar onde comecam os ponteiros lento e rapido, tens que validar o acesso intermedio do ponteiro rapido, ...

[mundo]

Será isto?

List break_list(List l){

   Lnode *lento = l, *rapido = l;

   while(rapido != NULL){
    lento = lento->next;
    rapido = rapido->next->next;
    if(rapido->next->next == NULL){
	    rapido = lento->next;
	    lento->next = NULL;
    }
   }
   return rapido;
}

Ou ainda está incompleto?

[HappyHippyHippo]

pelas respostas que estás a apresentar só posso depreender que não estás sequer a testar as hipóteses que apresentas

metes algo parecido com o que foi te explicado e parece nem sequer queres perceber o que está a acontecer

ao perceber, certos erros que aparecem no teu código nem sequer te passavam pela cabeça

[mundo]

Estou a testar, e a fazer com uma folha ao lado, acho que so falta colocar a info, so nao estou a colocar a main, porque é algo que onde estou a estudar nunca fizemos muito, para testar, supostamente com os meus rascunhos, penso que isso funcionaria

[HappyHippyHippo]

achas ?

experimenta com uma lista impar

[mundo]

Vou fazer o desenho com as iterações a ver se percebi, e juntar o codigo, e agradecia que me corrigissem por favor:

List break_list(List l){

   Lnode *lento = l, *rapido = l;

   while(rapido->next != NULL){
    lento = lento->next;
    rapido = rapido->next->next;
    if(rapido->next == NULL){
	    rapido = lento;
	    lento = NULL;
    }
   }
   return rapido;
}

Por exemplo a lista ligada impar: 1->2->3->4->5->6->7

inicializaçao: lento = 1, rapido = 1

1ª iteração: lento = 2, rapido = 3

2ªiteraçao: lento = 3, rapido = 5

3ª iteração: lento = 4, rapido = 7

o rapido passa a ser o local onde esta o lento

coloca o local onde o lento se encontra a nulo

4ª iteraçao: ja nao entra no while

A minha duvida prende-se na 3ª iteraçao, e se o if está correto

[HappyHippyHippo]

1º - atribuir NULL ao ponteiro "lento" não altera nada na lista, estás somente a alterar o valor do ponteiro.

2º - o ponteiro "rapido" fica com o valor de lento (4), mas no entanto continuas a não "partir" a lista

3º - agora experimenta com uma lista com um número par de elementos

[mundo]

Estou mesmo a nora, eu já percebi que caso a lista seja par, esse algoritmo nao funciona, sera que me podes dar mais um empurranzinho? com o a condiçao no if a ser rapido->next->next, passa a funcionar para listas pares também, não estou a conseguir partir a lista a metade