Bagaimana menemukan elemen tengah dari daftar tertaut dalam satu pass?

Salah satu pertanyaan paling populer dari struktur data dan algoritma, sebagian besar ditanyakan pada wawancara teleponi.

Dengan menipu, dan melakukan dua operan sekaligus, secara paralel. Tapi saya tidak tahu apakah perekrut akan menyukai ini.

Dapat dilakukan pada daftar tertaut tunggal, dengan trik yang bagus. Dua petunjuk perjalanan melintasi daftar, satu dengan kecepatan ganda. Ketika yang cepat mencapai akhir, yang lain setengah jalan.

Jika ini bukan daftar yang ditautkan dua kali lipat, Anda bisa saja menghitung dan menggunakan daftar, tetapi itu membutuhkan penggandaan memori Anda dalam kasus terburuk, dan itu tidak akan berfungsi jika daftar itu terlalu besar untuk disimpan dalam memori.

Solusi sederhana, hampir konyol, hanya meningkatkan simpul tengah setiap dua node

function middle(start) {
    var middle = start
    var nextnode = start
    var do_increment = false;
    while (nextnode.next != null) {
        if (do_increment) {
             middle = middle.next;
        }
        do_increment = !do_increment;
        nextnode = nextnode.next;
    }
    return middle;
}

Menguraikan jawaban Hendrik

Jika ini daftar yang ditautkan dua kali lipat, beralihlah dari kedua ujungnya

function middle(start, end) {
  do_advance_start = false;
  while(start !== end && start && end) {
     if (do_advance_start) {
        start = start.next
     }
     else {
        end = end.prev
     }
     do_advance_start = !do_advance_start
  }
  return (start === end) ? start : null;
}

Diberikan [1, 2, 3] => 2

1, 3
1, 2
2, 2

Diberikan [1, 2] => 1

1, 2
1, 1

Diberikan [1] => 1

Diberikan [] => null

Buat struktur dengan pointer yang mampu menunjuk ke node dari daftar tertaut dan dengan variabel integer yang menjaga jumlah jumlah node dalam daftar.

struct LL{
    struct node *ptr;
    int         count;
}start;

$start.ptr$$start.count = 1$
$start.count$

$start.count$

Buat array dinamis, di mana setiap elemen array adalah pointer ke setiap node dalam daftar dalam urutan melintasi, mulai dari awal. Buat integer, diinisialisasi ke 1, yang melacak berapa banyak node yang telah Anda kunjungi (kenaikan yang setiap kali Anda pergi ke node baru). Ketika Anda sampai di akhir, Anda tahu seberapa besar daftar itu, dan Anda memiliki array pointer ke setiap node. Akhirnya, bagi ukuran daftar dengan 2 (dan kurangi 1 untuk pengindeksan berbasis 0) dan ambil pointer yang disimpan dalam indeks array; jika ukuran daftar aneh, Anda dapat memilih elemen mana yang akan dikembalikan (saya masih akan mengembalikan yang pertama).

Berikut adalah beberapa kode Java yang mendapatkan titik (meskipun gagasan array dinamis akan menjadi agak miring). Saya akan memberikan C / C ++ tetapi saya sangat berkarat di daerah itu.

public Node getMiddleNode(List<Node> nodes){

    int size = 1;
    //add code to dynamically increase size if at capacity after adding
    Node[] pointers = new Node[10];

    for (int i = 0; i < nodes.size(); i++){
        //remember to dynamically allocate more space if needed
        pointers[i] = nodes.get(i);
        size++;
    }

    return pointers[(size - 1)/2];

}

Apakah rekursi dianggap lebih dari satu pass?

Lintasi daftar sampai akhir, melewati bilangan bulat dengan referensi. Buat salinan lokal dari nilai itu di setiap level untuk referensi di kemudian hari, dan tambahkan penghitungan referensi ke panggilan berikutnya.

Pada simpul terakhir, bagi hitungan dengan dua dan potong / lantai () hasilnya (jika Anda ingin simpul pertama menjadi "tengah" ketika hanya ada dua elemen) atau bulatkan (jika Anda ingin simpul kedua menjadi Tengah"). Gunakan indeks berbasis nol atau satu dengan tepat.

Unwinding, cocokkan hitungan ref dengan salinan lokal (yang merupakan nomor node). Jika sama, kembalikan simpul itu; lain kembalikan node yang dikembalikan dari panggilan rekursif.
.

Ada cara lain untuk melakukan ini; beberapa dari mereka mungkin kurang rumit (saya pikir saya melihat seseorang mengatakan membacanya menjadi sebuah array dan menggunakan panjang array untuk menentukan tengah - pujian). Tapi sejujurnya, tidak ada jawaban yang bagus, karena itu pertanyaan wawancara yang bodoh. Nomor satu, yang masih menggunakan daftar tertaut ( opini pendukung ); Dua, menemukan simpul tengah adalah latihan akademis yang sewenang-wenang tanpa nilai dalam skenario kehidupan nyata; Tiga, jika saya benar-benar perlu tahu simpul tengah, daftar tertaut saya akan memperlihatkan jumlah simpul. Ini lebih mudah untuk mempertahankan properti itu daripada membuang waktu melintasi seluruh daftar setiap kali saya ingin simpul tengah. Dan akhirnya, empat, setiap pewawancara akan menyukai atau menolak jawaban yang berbeda - apa yang menurut pewawancara licin, yang lain akan menyebut konyol.

Saya hampir selalu menjawab pertanyaan wawancara dengan lebih banyak pertanyaan. Jika saya mendapatkan pertanyaan seperti ini (saya tidak pernah punya), saya akan bertanya (1) Apa yang Anda simpan di daftar tertaut ini, dan apakah ada struktur yang lebih tepat untuk secara efisien mengakses node tengah jika memang benar-benar diperlukan untuk melakukannya ; (2) Apa kendala saya? Saya dapat membuatnya lebih cepat jika ingatan bukan masalah (mis. Jawaban array), tetapi jika pewawancara berpikir bahwa meningkatkan ingatan itu sia-sia, saya akan kena celaka. (3) Bahasa apa yang akan saya kembangkan? Hampir setiap bahasa modern yang saya tahu memiliki kelas bawaan untuk menangani daftar tertaut yang membuat melintasi daftar itu tidak perlu - mengapa menemukan kembali sesuatu yang telah disesuaikan untuk efisiensi oleh pengembang bahasa?

Dengan menggunakan 2 pointer. Tambahkan satu di setiap iterasi dan lainnya di setiap iterasi kedua. Ketika 1 pointer menunjuk ke akhir daftar yang ditautkan, pergi 2 pointer akan menunjuk ke mode tengah dari daftar yang terhubung.