Verifique se duas listas vinculadas se fundem. Se sim, onde?

Esta pergunta pode ser antiga, mas não consegui pensar em uma resposta.

Digamos, há duas listas de comprimentos diferentes, mescladas em um ponto ; como sabemos onde está o ponto de fusão?

Condições:

1. Não sabemos o comprimento
2. Devemos analisar cada lista apenas uma vez.

E se

• por "modificação não permitida" significava "você pode mudar, mas no final eles devem ser restaurados", e
• poderíamos iterar as listas exatamente duas vezes

o seguinte algoritmo seria a solução.

Primeiro, os números. Suponha que a primeira lista seja longa a+ce a segunda seja longa b+c, onde cé o comprimento de sua "cauda" comum (após o ponto de fusão). Vamos denotá-los da seguinte forma:

x = a+c
y = b+c

Como não sabemos o comprimento, calcularemos xe ysem iterações adicionais; você verá como.

Em seguida, iteramos cada lista e as revertemos durante a iteração! Se os dois iteradores alcançarem o ponto de fusão ao mesmo tempo, descobrimos isso por meio de uma simples comparação. Caso contrário, um ponteiro alcançará o ponto de fusão antes do outro.

Depois disso, quando o outro iterador atingir o ponto de fusão, ele não prosseguirá para a cauda comum. Em vez disso, irá voltar para o início anterior da lista que atingiu o ponto de fusão antes! Portanto, antes de atingir o final da lista alterada (ou seja, o primeiro início da outra lista), ele fará as a+b+1iterações totais. Vamos encerrar z+1.

O ponteiro que alcançou o ponto de mesclagem primeiro, continuará iterando, até atingir o final da lista. O número de iterações feitas deve ser calculado e é igual a x.

Em seguida, esse ponteiro itera de volta e reverte as listas novamente. Mas agora não vai voltar para o início da lista da qual originalmente começou! Em vez disso, irá para o início da outra lista! O número de iterações feitas deve ser calculado e igual a y.

Portanto, sabemos os seguintes números:

x = a+c
y = b+c
z = a+b

A partir do qual determinamos que

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

O que resolve o problema.

O que segue é de longe o maior de todos que já vi - O (N), sem contadores. Eu consegui durante uma entrevista a um candidato a SN na VisionMap .

Faça um ponteiro de interação como este: ele avança todas as vezes até o fim, e então pula para o início da lista oposta e assim por diante. Crie dois desses, apontando para duas cabeças. Avance cada um dos ponteiros em 1 a cada vez, até que eles se encontrem. Isso acontecerá após uma ou duas passagens.

Eu ainda uso essa pergunta nas entrevistas - mas para ver quanto tempo leva para alguém entender porque essa solução funciona.

A resposta de Pavel requer modificação das listas , bem como iterar cada lista duas vezes.

Aqui está uma solução que requer apenas a iteração de cada lista duas vezes (a primeira vez para calcular seu comprimento; se o comprimento for fornecido, você só precisa iterar uma vez).

A ideia é ignorar as entradas iniciais da lista mais longa (o ponto de fusão não pode estar lá), de modo que os dois ponteiros fiquem a uma distância igual do final da lista. Em seguida, mova-os para a frente até que se fundam.

lenA = count(listA) //iterates list A
lenB = count(listB) //iterates list B

ptrA = listA
ptrB = listB

//now we adjust either ptrA or ptrB so that they are equally far from the end
while(lenA > lenB):
    ptrA = ptrA->next
    lenA--
while(lenB > lenA):
    prtB = ptrB->next
    lenB--

while(ptrA != NULL):
    if (ptrA == ptrB):
        return ptrA //found merge point
    ptrA = ptrA->next
    ptrB = ptrB->next

Isso é assintoticamente o mesmo (tempo linear) que minha outra resposta, mas provavelmente tem constantes menores, então é provavelmente mais rápido. Mas acho que minha outra resposta é mais legal.

Bem, se você sabe que eles vão se fundir:

Digamos que você comece com:

A-->B-->C
        |
        V
1-->2-->3-->4-->5

1) Percorra a primeira lista definindo cada ponteiro seguinte como NULL.

Agora você tem:

A   B   C

1-->2-->3   4   5

2) Agora vá até a segunda lista e espere até ver um NULL, que é o seu ponto de fusão.

Se você não tiver certeza de que eles se fundem, pode usar um valor de sentinela para o valor do ponteiro, mas isso não é tão elegante.

Se pudéssemos iterar as listas exatamente duas vezes, posso fornecer um método para determinar o ponto de fusão:

• iterar ambas as listas e calcular os comprimentos A e B
• calcular a diferença de comprimentos C = | AB |;
• comece a iterar ambas as listas simultaneamente, mas faça etapas C adicionais na lista que era maior
• estes dois ponteiros se encontrarão no ponto de fusão

Aqui está uma solução, computacionalmente rápida (itera cada lista uma vez), mas usa muita memória:

for each item in list a
  push pointer to item onto stack_a

for each item in list b
  push pointer to item onto stack_b

while (stack_a top == stack_b top) // where top is the item to be popped next
  pop stack_a
  pop stack_b

// values at the top of each stack are the items prior to the merged item

Você pode usar um conjunto de nós. Faça a iteração em uma lista e adicione cada nó ao conjunto. Em seguida, itere através da segunda lista e para cada iteração, verifique se o Nó existe no conjunto. Em caso afirmativo, você encontrou seu ponto de fusão :)

Isso viola a condição "analise cada lista apenas uma vez", mas implemente o algoritmo da tartaruga e da lebre (usado para encontrar o ponto de fusão e a duração do ciclo de uma lista cíclica), então você começa na Lista A e quando atinge o NULL no end você finge que é um ponteiro para o início da lista B, criando assim a aparência de uma lista cíclica. O algoritmo então dirá exatamente a que ponto abaixo da Lista A está a mesclagem (a variável 'mu' de acordo com a descrição da Wikipedia).

Além disso, o valor "lambda" informa o comprimento da lista B e, se desejar, você pode calcular o comprimento da lista A durante o algoritmo (quando redirecionar o link NULL).

Talvez eu esteja simplificando demais isso, mas simplesmente itere a menor lista e use os últimos nós Linkcomo o ponto de fusão?

Então, onde Data->Link->Link == NULLestá o ponto final, dando Data->Linkcomo ponto de fusão (no final da lista).

EDITAR:

Ok, a partir da imagem que você postou, você analisa as duas listas, a menor primeiro. Com a menor lista, você pode manter as referências ao nó a seguir. Agora, quando você analisa a segunda lista, faz uma comparação na referência para descobrir onde Referência [i] é a referência em LinkedList [i] -> Link. Isso dará o ponto de fusão. Hora de explicar com fotos (sobrepor os valores na foto do OP).

Você tem uma lista vinculada (referências mostradas abaixo):

A->B->C->D->E

Você tem uma segunda lista vinculada:

1->2->

Com a lista mesclada, as referências seriam as seguintes:

1->2->D->E->

Portanto, você mapeia a primeira lista "menor" (como a lista mesclada, que é o que estamos contando, tem um comprimento de 4 e a lista principal 5)

Faça um loop pela primeira lista, mantenha uma referência de referências.

A lista conterá as seguintes referências Pointers { 1, 2, D, E }.

Vamos agora para a segunda lista:

-> A - Contains reference in Pointers? No, move on
-> B - Contains reference in Pointers? No, move on
-> C - Contains reference in Pointers? No, move on
-> D - Contains reference in Pointers? Yes, merge point found, break.

Claro, você mantém uma nova lista de indicadores, mas isso não está fora das especificações. No entanto, a primeira lista é analisada exatamente uma vez, e a segunda lista só será totalmente analisada se não houver ponto de fusão. Caso contrário, ele terminará mais cedo (no ponto de fusão).

Eu testei um caso de mesclagem no meu FC9 x86_64 e imprimo cada endereço de nó conforme mostrado abaixo:

Head A 0x7fffb2f3c4b0
0x214f010
0x214f030
0x214f050
0x214f070
0x214f090
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170


Head B 0x7fffb2f3c4a0
0x214f0b0
0x214f0d0
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170

Note que eu havia alinhado a estrutura do nó, então quando malloc () um nó, o endereço é alinhado com 16 bytes, veja pelo menos 4 bits. Os bits mínimos são 0s, ou seja, 0x0 ou 000b. Portanto, se você estiver no mesmo caso especial (endereço de nó alinhado) também, você pode usar pelo menos 4 bits. Por exemplo, ao viajar ambas as listas de ponta a ponta, defina 1 ou 2 dos 4 bits do endereço do nó visitante, ou seja, defina um sinalizador;

next_node = node->next;
node = (struct node*)((unsigned long)node | 0x1UL);

Observe que os sinalizadores acima não afetarão o endereço do nó real, mas apenas o valor do ponteiro do nó SALVO.

Uma vez encontrado, alguém definiu o (s) bit (s) de sinalizador (es), o primeiro nó encontrado deve ser o ponto de fusão. depois de fazer isso, você restauraria o endereço do nó limpando os bits de sinalização que você definiu. enquanto uma coisa importante é que você deve ter cuidado ao iterar (por exemplo, node = node-> next) para fazer a limpeza. lembre-se de que você configurou bits de sinalização, então faça desta forma

real_node = (struct node*)((unsigned long)node) & ~0x1UL);
real_node = real_node->next;
node = real_node;

Como essa proposta irá restaurar os endereços de nó modificados, ela pode ser considerada como "sem modificação".

Pode haver uma solução simples, mas exigirá um espaço auxiliar. A ideia é percorrer uma lista e armazenar cada endereço em um mapa hash, agora percorrer a outra lista e comparar se o endereço está no mapa hash ou não. Cada lista é percorrida apenas uma vez. Não há modificação em nenhuma lista. O comprimento ainda é desconhecido. Espaço auxiliar usado: O (n) onde 'n' é o comprimento da primeira lista percorrida.

esta solução itera cada lista apenas uma vez ... nenhuma modificação da lista também é necessária ... embora você possa reclamar de espaço ..
1) Basicamente, você itera na lista1 e armazena o endereço de cada nó em uma matriz (que armazena o valor int não assinado)
2) Em seguida, você itera a lista2, e para o endereço de cada nó ---> você pesquisa através do array que encontrou uma correspondência ou não ... se o fizer, então este é o nó de fusão

//pseudocode
//for the first list
p1=list1;
unsigned int addr[];//to store addresses
i=0;
while(p1!=null){
  addr[i]=&p1;
  p1=p1->next;
}
int len=sizeof(addr)/sizeof(int);//calculates length of array addr
//for the second list
p2=list2;
while(p2!=null){
  if(search(addr[],len,&p2)==1)//match found
  {
    //this is the merging node
    return (p2);
  }
  p2=p2->next;
}

int search(addr,len,p2){
  i=0;  
  while(i<len){
    if(addr[i]==p2)
      return 1;
    i++;
  }
 return 0;
} 

Espero que seja uma solução válida ...

Não há necessidade de modificar nenhuma lista. Existe uma solução em que só temos que percorrer cada lista uma vez.

1. Crie duas pilhas, digamos stck1 e stck2.
2. Percorra a primeira lista e envie uma cópia de cada nó percorrido em stck1.
3. Igual à etapa dois, mas desta vez atravesse a 2ª lista e envie a cópia dos nós em stck2.
4. Agora, clique em ambas as pilhas e verifique se os dois nós são iguais, se sim, mantenha uma referência a eles. Se não, os nós anteriores que eram iguais são, na verdade, o ponto de fusão que estávamos procurando.

int FindMergeNode(Node headA, Node headB) {
  Node currentA = headA;
  Node currentB = headB;

  // Do till the two nodes are the same
  while (currentA != currentB) {
    // If you reached the end of one list start at the beginning of the other
    // one currentA
    if (currentA.next == null) {
      currentA = headA;
    } else {
      currentA = currentA.next;
    }
    // currentB
    if (currentB.next == null) {
      currentB = headB;
    } else {
      currentB = currentB.next;
    }
  }
  return currentB.data;
}

Aqui está uma solução ingênua, não é necessário percorrer listas inteiras.

se o seu nó estruturado tem três campos como

struct node {
    int data;   
    int flag;  //initially set the flag to zero  for all nodes
    struct node *next;
};

digamos que você tenha duas cabeças (cabeça1 e cabeça2) apontando para a cabeça de duas listas.

Percorra a lista no mesmo ritmo e coloque o sinalizador = 1 (sinalizador visitado) para esse nó,

  if (node->next->field==1)//possibly longer list will have this opportunity
      //this will be your required node. 

Que tal agora:

1. Se você só tem permissão para percorrer cada lista apenas uma vez, pode criar um novo nó, percorrer a primeira lista para que cada nó aponte para este novo nó e percorrer a segunda lista para ver se algum nó está apontando para seu novo nó ( esse é o seu ponto de fusão). Se a segunda travessia não levar ao seu novo nó, as listas originais não têm um ponto de fusão.

2. Se você tiver permissão para percorrer as listas mais de uma vez, poderá percorrer cada lista para encontrar nossos comprimentos e, se forem diferentes, omita os nós "extras" no início da lista mais longa. Em seguida, basta percorrer as duas listas, uma etapa de cada vez, e encontrar o primeiro nó de fusão.

Etapas em Java:

1. Crie um mapa.
2. Comece a percorrer os dois ramos da lista e coloque todos os nós percorridos da lista no mapa usando alguma coisa única relacionada aos nós (digamos a Id do nó) como chave e coloque os valores como 1 no início para todos.
3. Sempre que chegar a primeira chave duplicada, aumente o valor dessa chave (digamos que agora seu valor se tornou 2, que é> 1.
4. Obtenha a chave onde o valor é maior que 1 e esse deve ser o nó onde duas listas estão se fundindo.

Podemos resolvê-lo com eficiência introduzindo o campo "isVisited". Percorra a primeira lista e defina o valor "isVisited" como "true" para todos os nós até o final. Agora comece a partir do segundo e encontre o primeiro nó onde flag é verdadeiro e Boom, seu ponto de fusão.

Etapa 1: encontre o comprimento de ambas as listas Etapa 2: Encontre a diferença e mova a maior lista com a diferença Etapa 3: Agora as duas listas estarão em posições semelhantes. Etapa 4: percorrer a lista para encontrar o ponto de fusão

//Psuedocode
def findmergepoint(list1, list2):
lendiff = list1.length() > list2.length() : list1.length() - list2.length() ? list2.lenght()-list1.lenght()
biggerlist = list1.length() > list2.length() : list1 ? list2  # list with biggest length
smallerlist = list1.length() < list2.length() : list2 ? list1 # list with smallest length


# move the biggest length to the diff position to level both the list at the same position
for i in range(0,lendiff-1):
    biggerlist = biggerlist.next
#Looped only once.  
while ( biggerlist is not None and smallerlist is not None ):
    if biggerlist == smallerlist :
        return biggerlist #point of intersection


return None // No intersection found

int FindMergeNode(Node *headA, Node *headB)
{
    Node *tempB=new Node;
    tempB=headB;
   while(headA->next!=NULL)
       {
       while(tempB->next!=NULL)
           {
           if(tempB==headA)
               return tempB->data;
           tempB=tempB->next;
       }
       headA=headA->next;
       tempB=headB;
   }
    return headA->data;
}

Use o mapa ou o dicionário para armazenar o endereço e o valor do nó. se o endereço já existe no Mapa / Dicionário, o valor da chave é a resposta. Eu fiz isso:

int FindMergeNode(Node headA, Node headB) {

Map<Object, Integer> map = new HashMap<Object, Integer>();

while(headA != null || headB != null)
{
    if(headA != null && map.containsKey(headA.next))
    {
        return map.get(headA.next);
    }

    if(headA != null && headA.next != null)
    {
         map.put(headA.next, headA.next.data);
         headA = headA.next;
    }

    if(headB != null && map.containsKey(headB.next))
    {
        return map.get(headB.next);
    }

    if(headB != null && headB.next != null)
    {
        map.put(headB.next, headB.next.data);
        headB = headB.next;
    }
}

return 0;
}

Solução de complexidade AO (n). Mas com base em uma suposição.

a suposição é: ambos os nós têm apenas inteiros positivos.

lógica: torne todos os inteiros da lista1 negativos. Em seguida, percorra a lista2, até obter um número inteiro negativo. Uma vez encontrado => pegue, mude o sinal de volta para positivo e retorne.

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {

    SinglyLinkedListNode current = head1; //head1 is give to be not null.

    //mark all head1 nodes as negative
    while(true){
        current.data = -current.data;
        current = current.next;
        if(current==null) break;
    }

    current=head2; //given as not null
    while(true){
        if(current.data<0) return -current.data;
        current = current.next;
    }

}

Podemos usar dois ponteiros e mover-nos de tal forma que se um dos ponteiros for nulo o apontamos para o cabeçalho da outra lista e o mesmo para o outro, desta forma se os comprimentos da lista forem diferentes eles se encontrarão na segunda passagem . Se o comprimento da lista1 for ne lista2 for m, sua diferença será d = abs (nm). Eles cobrirão essa distância e se encontrarão no ponto de fusão.
Código:

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedListNode* start1=head1;
    SinglyLinkedListNode* start2=head2;
    while (start1!=start2){
        start1=start1->next;
        start2=start2->next;
        if (!start1)
        start1=head2;
        if (!start2)
        start2=head1;
    }
    return start1->data;
}

Você pode adicionar os nós de list1a um hashset e o loop através do segundo e se algum nó de list2já estiver presente no conjunto. Se sim, então esse é o nó de mesclagem

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    HashSet<SinglyLinkedListNode> set=new HashSet<SinglyLinkedListNode>();
    while(head1!=null)
    {
        set.add(head1);
        head1=head1.next;
    }
    while(head2!=null){
        if(set.contains(head2){
            return head2.data;
        }
    }
    return -1;
}

Solução usando javascript

var getIntersectionNode = function(headA, headB) {
    
    if(headA == null || headB == null) return null;
    
    let countA = listCount(headA);
    let countB = listCount(headB);
    
    let diff = 0;
    if(countA > countB) {

        diff = countA - countB;
        for(let i = 0; i < diff; i++) {
            headA = headA.next;
        }
    } else if(countA < countB) {
        diff = countB - countA;
        for(let i = 0; i < diff; i++) {
            headB = headB.next;
        }
    }

    return getIntersectValue(headA, headB);
};

function listCount(head) {
    let count = 0;
    while(head) {
        count++;
        head = head.next;
    }
    return count;
}

function getIntersectValue(headA, headB) {
    while(headA && headB) {
        if(headA === headB) {
            return headA;
        }
        headA = headA.next;
        headB = headB.next;
    }
    return null;
}

Se a edição da lista vinculada for permitida,

1. Em seguida, apenas torne os próximos ponteiros de nó de todos os nós da lista 2 como nulos.
2. Encontre o valor de dados do último nó da lista 1. Isso fornecerá o nó de interseção em uma única travessia de ambas as listas, sem "lógica de alta fidelidade".