Periksa apakah dua daftar tertaut bergabung. Jika ya, dimana?

Pertanyaan ini mungkin sudah lama, tapi saya tidak bisa menemukan jawabannya.

Katakanlah, ada dua daftar dengan panjang yang berbeda, bergabung pada satu titik ; bagaimana kita tahu dimana titik penggabungannya?

Kondisi:

1. Kami tidak tahu panjangnya
2. Kita harus mengurai setiap daftar hanya sekali.

Jika

• dengan "modifikasi tidak diperbolehkan" itu berarti "Anda dapat berubah tetapi pada akhirnya mereka harus dikembalikan", dan
• kami dapat mengulang daftar tersebut tepat dua kali

algoritma berikut akan menjadi solusinya.

Pertama, angkanya. Asumsikan daftar pertama panjang a+cdan daftar kedua panjang b+c, di mana cpanjang "ekor" mereka (setelah titik gabungan). Mari kita tunjukkan sebagai berikut:

x = a+c
y = b+c

Karena kita tidak mengetahui panjangnya, kita akan menghitung xdan ytanpa iterasi tambahan; Anda akan melihat caranya.

Kemudian, kami mengulang setiap daftar dan membalikkannya saat melakukan iterasi! Jika kedua iterator mencapai titik penggabungan pada saat yang sama, maka kami menemukannya hanya dengan membandingkan. Jika tidak, satu penunjuk akan mencapai titik gabungan sebelum penunjuk lainnya.

Setelah itu, ketika iterator lain mencapai titik penggabungan, itu tidak akan dilanjutkan ke ekor yang sama. Sebaliknya akan kembali ke awal awal daftar yang telah mencapai titik gabungan sebelumnya! Jadi, sebelum mencapai akhir dari daftar yang diubah (yaitu awal awal dari daftar lainnya), dia akan membuat a+b+1iterasi total. Sebut saja z+1.

Penunjuk yang mencapai titik gabungan pertama, akan terus melakukan iterasi, hingga mencapai akhir daftar. Jumlah iterasi yang dibuat harus dihitung dan sama dengan x.

Kemudian, penunjuk ini mengulang kembali dan membalik daftar lagi. Tapi sekarang itu tidak akan kembali ke awal daftar semula! Sebaliknya, ini akan pergi ke awal daftar lainnya! Jumlah iterasi yang dibuat harus dihitung dan sama dengany .

Jadi kita tahu angka-angka berikut:

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

Dari mana kami menentukan itu

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

Yang memecahkan masalah.

Berikut ini adalah yang terbesar dari semua yang pernah saya lihat - O (N), tidak ada penghitung. Saya mendapatkannya saat wawancara dengan kandidat SN di VisionMap .

Buatlah penunjuk antar seperti ini: ia maju setiap kali sampai akhir, lalu melompat ke awal daftar yang berlawanan, dan seterusnya. Buat dua ini, menunjuk ke dua kepala. Tingkatkan tiap pointer sebanyak 1 setiap kali, sampai bertemu. Ini akan terjadi setelah satu atau dua operan.

Saya masih menggunakan pertanyaan ini dalam wawancara - tetapi untuk melihat berapa lama seseorang memahami mengapa solusi ini berhasil.

Jawaban Pavel membutuhkan modifikasi daftar serta mengulang setiap daftar dua kali.

Berikut adalah solusi yang hanya membutuhkan iterasi setiap daftar dua kali (pertama kali menghitung panjangnya; jika panjangnya diberikan, Anda hanya perlu mengulanginya sekali).

Idenya adalah mengabaikan entri awal dari daftar yang lebih panjang (titik gabungan tidak boleh ada di sana), sehingga kedua penunjuk memiliki jarak yang sama dari akhir daftar. Kemudian pindahkan ke depan sampai menyatu.

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

Ini secara asimtotik sama (waktu linier) dengan jawaban saya yang lain tetapi mungkin memiliki konstanta yang lebih kecil, jadi mungkin lebih cepat. Tapi saya pikir jawaban saya yang lain lebih keren.

Nah, jika Anda tahu bahwa keduanya akan bergabung:

Katakanlah Anda mulai dengan:

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

1) Pergi melalui pengaturan daftar pertama setiap penunjuk berikutnya ke NULL.

Sekarang kamu punya:

A   B   C

1-->2-->3   4   5

2) Sekarang pergi melalui daftar kedua dan tunggu sampai Anda melihat NULL, itu adalah titik penggabungan Anda.

Jika Anda tidak dapat memastikan bahwa mereka bergabung, Anda dapat menggunakan nilai sentinel untuk nilai penunjuk, tapi itu tidak elegan.

Jika kita bisa mengulang daftar tepat dua kali, maka saya bisa memberikan metode untuk menentukan titik penggabungan:

• iterasi kedua daftar dan hitung panjang A dan B
• menghitung selisih panjang C = | AB |;
• mulai iterasi kedua daftar secara bersamaan, tetapi buat langkah C tambahan pada daftar yang lebih besar
• kedua petunjuk ini akan saling bertemu di titik penggabungan

Berikut solusinya, secara komputasi cepat (mengulang setiap daftar satu kali) tetapi menggunakan banyak memori:

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

Anda dapat menggunakan satu set Node. Iterasi melalui satu daftar dan tambahkan setiap Node ke set. Kemudian lakukan iterasi melalui daftar kedua dan untuk setiap iterasi, periksa apakah Node ada di set. Jika ya, Anda telah menemukan titik penggabungan Anda :)

Ini bisa dibilang melanggar ketentuan "parse setiap daftar hanya sekali", tetapi menerapkan algoritme kura - kura dan kelinci (digunakan untuk menemukan titik penggabungan dan panjang siklus daftar siklik) sehingga Anda mulai dari Daftar A, dan ketika Anda mencapai NULL di akhir Anda berpura-pura itu adalah penunjuk ke awal daftar B, sehingga menciptakan tampilan daftar siklik. Algoritme kemudian akan memberi tahu Anda dengan tepat seberapa jauh daftar A penggabungan (variabel 'mu' menurut deskripsi Wikipedia).

Selain itu, nilai "lambda" memberi tahu Anda panjang daftar B, dan jika Anda mau, Anda dapat menghitung panjang daftar A selama algoritme (saat Anda mengarahkan ulang tautan NULL).

Mungkin saya terlalu menyederhanakan ini, tetapi hanya mengulang daftar terkecil dan menggunakan node terakhir Linksebagai titik penggabungan?

Jadi, di mana Data->Link->Link == NULLtitik akhirnya, memberi Data->Linksebagai titik penggabungan (di akhir daftar).

EDIT:

Oke, dari gambar yang kamu posting tadi kamu parse dua list, yang terkecil dulu. Dengan daftar terkecil Anda dapat mempertahankan referensi ke node berikut. Sekarang, ketika Anda mengurai daftar kedua Anda melakukan perbandingan pada referensi untuk menemukan di mana Referensi [i] adalah referensi di LinkedList [i] -> Link. Ini akan memberikan titik penggabungan. Saatnya menjelaskan dengan gambar (tumpang tindih nilai pada gambar OP).

Anda memiliki daftar tertaut (referensi ditunjukkan di bawah):

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

Anda memiliki daftar tertaut kedua:

1->2->

Dengan daftar yang digabungkan, referensi akan menjadi sebagai berikut:

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

Oleh karena itu, Anda memetakan daftar "kecil" pertama (sebagai daftar gabungan, yang kami hitung memiliki panjang 4 dan daftar utama 5)

Ulangi daftar pertama, pertahankan referensi referensi.

Daftar tersebut akan berisi referensi berikut Pointers { 1, 2, D, E }.

Kami sekarang melalui daftar kedua:

-> 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.

Tentu, Anda mempertahankan daftar petunjuk baru, tapi itu tidak di luar spesifikasi. Namun daftar pertama diurai tepat satu kali, dan daftar kedua hanya akan diurai sepenuhnya jika tidak ada titik penggabungan. Jika tidak, ini akan berakhir lebih cepat (di titik penggabungan).

Saya telah menguji kasus penggabungan pada FC9 x86_64 saya, dan mencetak setiap alamat node seperti yang ditunjukkan di bawah ini:

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


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

Catatan karena saya telah menyelaraskan struktur node, jadi ketika malloc () sebuah node, alamatnya sejajar w / 16 byte, lihat paling sedikit 4 bit. Bit terkecil adalah 0s, yaitu 0x0 atau 000b. Jadi jika Anda berada dalam kasus khusus yang sama (alamat node selaras) juga, Anda dapat menggunakan minimal 4 bit ini. Misalnya ketika melakukan perjalanan kedua daftar dari kepala ke ekor, setel 1 atau 2 dari 4 bit alamat node kunjungan, yaitu, setel bendera;

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

Catatan di atas bendera tidak akan mempengaruhi alamat node yang sebenarnya tetapi hanya nilai penunjuk node TERSIMPAN Anda.

Setelah ditemukan seseorang telah mengatur bit flag, maka node pertama yang ditemukan harus menjadi titik penggabungan. setelah selesai, Anda akan mengembalikan alamat node dengan menghapus bit bendera yang telah Anda tetapkan. sementara yang penting adalah Anda harus berhati-hati saat melakukan iterasi (misalnya node = node-> next) untuk melakukan pembersihan. ingat Anda telah menetapkan bit bendera, jadi lakukan dengan cara ini

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

Karena proposal ini akan memulihkan alamat node yang diubah, ini dapat dianggap sebagai "tidak ada modifikasi".

Mungkin ada solusi sederhana tetapi akan membutuhkan ruang tambahan. Idenya adalah melintasi daftar dan menyimpan setiap alamat dalam peta hash, sekarang melintasi daftar lain dan cocok jika alamat tersebut ada di peta hash atau tidak. Setiap daftar hanya ditelusuri sekali. Tidak ada modifikasi pada daftar mana pun. Panjangnya masih belum diketahui. Ruang bantu yang digunakan: O (n) dengan 'n' adalah panjang list pertama yang dilalui.

solusi ini mengulang setiap daftar hanya sekali ... tidak ada modifikasi daftar yang diperlukan juga .. meskipun Anda mungkin mengeluh tentang ruang ..
1) Pada dasarnya Anda mengulang dalam list1 dan menyimpan alamat setiap node dalam sebuah array (yang menyimpan nilai int unsigned)
2) Kemudian Anda mengulang list2, dan untuk setiap alamat node ---> Anda mencari melalui array yang Anda temukan cocok atau tidak ... jika Anda melakukannya maka ini adalah node penggabungan

//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;
} 

Semoga ini solusi yang valid ...

Tidak perlu mengubah daftar apa pun. Ada solusi di mana kita hanya perlu melintasi setiap daftar satu kali.

1. Buat dua tumpukan, katakanlah stck1 dan stck2.
2. Lintasi daftar pertama dan dorong salinan setiap node yang Anda lintasi di stck1.
3. Sama seperti langkah kedua tetapi kali ini melintasi daftar ke-2 dan mendorong salinan node di stck2.
4. Sekarang, pop dari kedua tumpukan dan periksa apakah kedua node sama, jika ya maka pertahankan referensi ke sana. Jika tidak, maka node sebelumnya yang sama sebenarnya adalah titik penggabungan yang kita cari.

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;
}

Inilah solusi naif, Tidak perlu melintasi seluruh daftar.

jika node terstruktur Anda memiliki tiga bidang seperti

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

katakanlah Anda memiliki dua kepala (head1 dan head2) yang menunjuk ke head dari dua daftar.

Lintasi kedua daftar dengan kecepatan yang sama dan letakkan bendera = 1 (bendera yang dikunjungi) untuk simpul itu,

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

Bagaimana dengan ini:

1. Jika Anda hanya diperbolehkan melintasi setiap daftar hanya sekali, Anda dapat membuat simpul baru, melintasi daftar pertama untuk memiliki setiap titik simpul ke simpul baru ini, dan melintasi daftar kedua untuk melihat apakah ada simpul yang menunjuk ke simpul baru Anda ( itulah titik penggabungan Anda). Jika traversal kedua tidak mengarah ke node baru Anda, daftar asli tidak memiliki titik penggabungan.

2. Jika Anda diizinkan melintasi daftar lebih dari satu kali, Anda dapat melintasi setiap daftar untuk menemukan panjangnya dan jika berbeda, hilangkan simpul "ekstra" di awal daftar yang lebih panjang. Kemudian telusuri kedua daftar satu per satu dan temukan node penggabungan pertama.

Langkah-langkah di Java:

1. Buat peta.
2. Mulai traverse di kedua cabang daftar dan Letakkan semua node daftar yang dilintasi ke dalam Peta menggunakan beberapa hal unik yang terkait dengan Nodes (misalnya node Id) sebagai Key dan letakkan Nilai sebagai 1 di awal untuk semua.
3. Ketika kunci duplikat pertama datang, tambahkan nilai untuk Kunci itu (katakanlah sekarang nilainya menjadi 2 yaitu> 1.
4. Dapatkan Kunci di mana nilainya lebih besar dari 1 dan itu seharusnya menjadi simpul tempat dua daftar bergabung.

Kami dapat menyelesaikannya secara efisien dengan memperkenalkan bidang "isVisited". Lintasi daftar pertama dan setel nilai "isVisited" ke "true" untuk semua node hingga akhir. Sekarang mulai dari yang kedua dan temukan node pertama di mana flag benar dan Boom, itu adalah titik penggabungan Anda.

Langkah 1: temukan panjang kedua daftar Langkah 2: Temukan perbedaan dan pindahkan daftar terbesar dengan perbedaan Langkah 3: Sekarang kedua daftar akan berada pada posisi yang sama. Langkah 4: Iterasi melalui daftar untuk menemukan titik penggabungan

//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;
}

Gunakan Peta atau Kamus untuk menyimpan nilai alamat vs node. Jika alamat tersebut sudah ada di Map / Dictionary maka nilai kuncinya adalah jawabannya. Saya melakukan ini:

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;
}

Solusi kompleksitas AO (n). Tapi berdasarkan asumsi.

asumsinya adalah: kedua node hanya memiliki bilangan bulat positif.

logika: buat semua bilangan bulat list1 menjadi negatif. Kemudian telusuri list2, sampai Anda mendapatkan bilangan bulat negatif. Setelah ditemukan => ambillah, ubah tandanya kembali menjadi positif dan return.

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;
    }

}

Kita dapat menggunakan dua penunjuk dan bergerak dengan cara sedemikian rupa sehingga jika salah satu penunjuk adalah nol, kita mengarahkannya ke kepala daftar lainnya dan sama untuk yang lain, dengan cara ini jika panjang daftar berbeda, mereka akan bertemu di lintasan kedua. . Jika panjang list1 adalah n dan list2 adalah m, selisihnya adalah d = abs (nm). Mereka akan menempuh jarak ini dan bertemu di titik penggabungan.
Kode:

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;
}

Anda dapat menambahkan node dari list1ke hashset dan loop melalui detik dan jika ada node dari list2sudah ada di set. Jika ya, maka itu node gabungan

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;
}

Solusi menggunakan 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;
}

Jika mengedit daftar tertaut diperbolehkan,

1. Kemudian buat saja penunjuk node berikutnya dari semua node dari daftar 2 sebagai null.
2. Temukan nilai data dari simpul terakhir dari daftar 1. Ini akan memberi Anda simpul yang berpotongan dalam satu traversal dari kedua daftar, dengan "tanpa logika hi fi".