Likou yang dipilih, pertanyaan tes permukaan Niukelian

Soal tes permukaan Likou dan Niukelian yang dipilih

2024-07-12

💎 欢迎各位大佬互三：halaman rumah saya

1. Membalikkan daftar tertaut

Berpikir: Jika Anda tidak membuka ruang tambahan dan hanya mengubah daftar tertaut asli, metode apa yang harus digunakan?

Mulailah dari elemen kedua dan lakukan penyisipan kepala secara berurutan.

Kemudian ubah saja referensinya, dan arahkan elemen terakhir ke null


class Solution {
    public ListNode reverseList(ListNode head) {
        //head为null，直接返回
        if(head == null){
            return head;
        }
 
        ListNode cur = head.next;
        //head变为了末尾元素，指向null
        head.next = null;
        while(cur!=null){
            //curn为cur的next节点，便于往后移动
            ListNode curn = cur.next;    
            cur.next = head;
            head = cur;
            //更新cur
            cur = curn;
        }
        return head;
    }
}

2. Node tengah dari daftar tertaut

876. Node perantara dari daftar tertaut

Metode pertama yang terlintas dalam pikiran untuk pertanyaan ini adalah dengan menentukan cnt, menelusuri daftar tertaut satu kali, lalu mencari angka tengahnya, lalu menelusuri nilai yang dikembalikan daftar tertaut hanya sekali untuk menemukan simpul perantara?

Inilah ide baru: gunakan penunjuk cepat dan lambat, mulai dari kepala. Penunjuk cepat menggerakkan dua titik setiap kali, dan penunjuk lambat menggerakkan satu titik setiap kali.

Kalau begitu mari kita terapkan:


class Solution {
    public ListNode middleNode(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast!= null&&fast.next!= null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

Apakah ini akan lebih efisien?

3. Kembalikan node ke-k dari node terakhir

Pertanyaan wawancara 02.02. Kembalikan node ke-k dari yang terakhir

Hal pertama yang terlintas dalam pikiran untuk pertanyaan ini adalah melintasinya satu kali untuk mendapatkan panjang total, dan kemudian mencari simpul ke-k dari yang terakhir. Namun, berdasarkan pertanyaan sebelumnya, Anda dapat memikirkan metode lain: Demikian pula,Dengan menggunakan penunjuk cepat dan lambat, lepaskan fast go k-1 node terlebih dahulu, lalu slow dan fast go pada saat yang bersamaan. Jika fast berikutnya adalah null, artinya fast telah mencapai node terakhir, dan lambat saat ini adalah simpul ke-k dari bawah.

Pertanyaan ini menunjukkan bahwa input k adalah sah, sehingga tidak diperlukan penilaian tambahan. Bagaimana menilai apakah k ilegal, dan panjang linked list tidak dapat langsung ditemukan, sehingga lambat perlu menilai sambil berjalan.


class Solution {
    public int kthToLast(ListNode head, int k) {
        if (head == null) {
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;
        int cnt = 0;
        while (cnt != k - 1) {
            //判断k的合法性，虽然本题不用判断
            fast = fast.next;
            if(fast == null){
                return;
            }
            cnt++;
        }
        //slow和fast同时移动
 
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}

4. Gabungkan daftar tertaut

21. Gabungkan dua daftar tertaut yang diurutkan

Ide:Anda hanya perlu mendefinisikan node baru newH, lalu membandingkan val headA dan headB Untuk akhirnya menemukan node head dari daftar tertaut yang digabungkan, Anda juga perlu mendefinisikan tmp = newH, lalu siapa pun yang memiliki yang lebih kecil. tmp.next akan menunjuk ke sana.


class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode tmp = head;
    
        while(list1!=null&&list2!=null){
            if(list1.val < list2.val){
                tmp.next = list1;
                list1 = list1.next;
                tmp = tmp.next;
            }else{
                tmp.next = list2;
                list2 = list2.next;
                tmp = tmp.next;
            }
        }
        //判断剩余的情况
        if(list1!=null){
            tmp.next = list1;
        }else if(list2!=null){
            tmp.next = list2;
        }
        return head.next;
    }
}

5. Pemisahan daftar tertaut

Pemisahan daftar tertaut CM11

Ini adalah pertanyaan wawancara di Niuke. Maksud pertanyaannya adalah membagi linked list. Sisi kiri x lebih kecil dari x, dan sisi kanan lebih besar dari x.

Ide: Tetapkan simpul baru saat ini untuk melintasi daftar tertaut asli (untuk mencegah daftar tertaut asli diubah), masukkan segala sesuatu yang lebih besar dari x ke dalam daftar tertaut, masukkan segala sesuatu yang lebih kecil dari x ke dalam daftar tertaut, dan terakhir hubungkan keduanya daftar tertaut.


public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                //处理刚开始为null的情况
                if (bs == null) {
                    bs = be = cur;
                }else{
                    be.next = cur;
                    be = be.next;
                }
            }else{
                if(as == null){
                    as = ae = cur;
                }else{
                    ae.next = cur;
                    ae = ae.next;
                }
            }
            cur = cur.next;
        }
        //都是比x大的情况
        if(bs == null){
            return as;
        }
        be.next = as;
        //最后都要置为null，不然可能会报错
        if(as!=null){
            ae.next = null;
        }
        return bs;
    }
}

Perlu dicatat bahwa jika lebih besar dari x, yaitu bs = null, maka as akan dikembalikan secara langsung, dan jika as.next akhirnya disetel ke null

6. Struktur palindrom dari daftar tertaut OR36

Struktur palindrom OR36 dari daftar tertaut

Ini adalah pertanyaan dari Niuke, karena memiliki persyaratan kompleksitas waktu dan kompleksitas ruang, yang berarti Anda tidak dapat membuka array tambahan, jika tidak, kompleksitas ruang tidak akan teratasi, dan traversal normal akan memiliki kompleksitas O(n)

Idenya seperti ini: pertama-tama temukan node tengah yang lambat dari daftar tertaut, lalu balikkan bagian dari tengah ke akhir. Node kepala dilintasi ke belakang, dan simpul lambat juga dilintasi ke belakang nilainya berbeda, artinya tidak mengembalikan struktur teks

Membalikkan daftar tertaut dan menemukan simpul perantara telah dilakukan sebelumnya


public class PalindromeList {
    public boolean chkPalindrome(ListNode head) {
        if (head == null) {
            return true;
        }
        //找到中间节点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //从slow开始到末尾反转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curn = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curn;
        }
        //判断回文
        while (head != slow) {
            if (head.val != slow.val) {
                return false;
            }
            //判断偶数节点
            if (head.next == slow) {
                return true;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
}

Perlu dicatat bahwa terdapat juga perbedaan dalam penilaian daftar tertaut dari node bernomor ganjil dan daftar tertaut dari node bernomor genap.

Jika simpul bernomor genap dipindahkan ke atas maka akan menimbulkan loop tak terhingga, sehingga diperlukan penilaian tambahan untuk simpul bernomor genap.

7. Daftar tertaut berpotongan

160. Daftar tertaut berpotongan

Daftar tertaut yang berpotongan adalah transformasi yang mirip dengan "Y", seperti yang ditunjukkan pada gambar

Gambaran pada pertanyaan di bawah ini juga sangat jelas.

Ide: Karena apakah A pendek atau B pendek, perbedaan di antara keduanya adalah bagian sebelum perpotongan. Anda hanya perlu memindahkan daftar tertaut yang panjang dengan selisihnya, lalu kedua node daftar tertaut bergerak mundur pada saat yang bersamaan simpul yang identik akan berpotongan


public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl = headA;
        ListNode ps = headB;
        int cnta = 0,cntb = 0;
        //计算两个链表的长度
        while(pl!=null){
            pl = pl.next;
            cnta++;
        }
        while(ps!=null){
            ps = ps.next;
            cntb++;
        }
        //如果链表b长，就更新pl,ps
        int len = cnta - cntb;
        //上面求长度时pl,ps都为空了，所以这里再重新指向
        pl = headA;
        ps = headB;
        if(len < 0){
            pl = headB;
            ps = headA;
            len = cntb - cnta;
        }
        //移动差值
        while(len!=0){
            pl = pl.next;
            len--;
        }
        //找到相交节点
        while(pl!=ps){
            pl = pl.next;
            ps = ps.next;
        }
        //链表不相交的情况
        if(pl == null) return null;
        return pl;
    }
}

Yang terakhir, kita perlu menambahkan situasi disjoint. Meskipun kita dapat meneruskan pertanyaan ini tanpa menambahkannya, kita tetap perlu menambahkannya demi ketelitian.

8. Daftar tertaut melingkar

8.1 Tentukan apakah ada loop

141. Daftar tertaut melingkar

Cara menentukan apakah daftar tertaut memiliki siklus:Masih menggunakan penunjuk kecepatan, seperti halnya dua orang berlari di taman bermain, yang satu berlari cepat dan yang lainnya berlari perlahan. Karena taman bermain itu berbentuk ring, maka yang cepat pasti bisa melebihi yang lambat , tapi kalau bukan karena Tamaki, mereka tidak akan pernah bisa bertemu, seperti dewi yang tidak bisa kamu tangkap sekeras apa pun kamu mengejarnya.

Tapi ada situasi lain. Jika itu adalah sebuah cincin dengan dua node, dan penunjuk cepat yang ditentukan mengambil 3 langkah sekaligus dan penunjuk lambat mengambil 1 langkah pada satu waktu, maka keduanya tidak akan pernah bertemu.

Oleh karena itu, penunjuk yang ditentukan perlu menilai berapa banyak langkah yang mereka ambil setiap kali. Jika yang satu mengambil 2 langkah dan yang lain mengambil 1 langkah, mereka pasti akan bertemu.


public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return true;
        }
        return false;
    }
}

8.2 Kembalikan node di pintu masuk ring

142. Daftar Tautan Melingkar II

Kali ini Anda perlu mengetahui titik masuk ke dalam ring setelah menilai apakah itu cincin pada pertanyaan sebelumnya


public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        //判断环
        while(fast!=null&&fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        if(fast == null||fast.next == null) return null;
        slow = head;
        //寻找环
        while(slow!=fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

Yang perlu ditambahkan adalah:

Jika ringnya sangat kecil, hasil penyederhanaan akhir menjadi seperti di atas, namun kode aslinya masih bagus.

Berbagi teknologi