Teknologian jakaminen

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

💎 欢迎各位大佬互三：kotisivuni

1. Käänteinen linkitetty luettelo

206. Käänteinen linkitetty luettelo

Ajatteleminen: Jos et avaa lisätilaa ja muokkaa vain alkuperäistä linkitettyä luetteloa, mitä menetelmää tulisi käyttää?

Aloita vain toisesta elementistä ja suorita pään lisäys järjestyksessä.

Muokkaa sitten viittausta ja osoita viimeinen elementti tyhjäksi

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. Linkitetyn luettelon keskisolmu

876. Linkitetyn luettelon välisolmu

Ensimmäinen menetelmä, joka tulee mieleen tälle kysymykselle, on ehdottomasti määrittää cnt, kulkea linkitetyn luettelon läpi kerran, etsiä sitten keskimmäinen luku ja sitten kulkea paluuarvo. Tämä menetelmä on hyvin yksinkertainen, mutta entä jos sinun on käytävä läpi linkitetty luettelo vain kerran löytääksesi välisolmun?

Tässä on uusi idea: käytä nopeita ja hitaita osoittimia, alkaen päästä. Nopea osoitin siirtää joka kerta yhtä solmua. Saavuttaako tämä lopullisen tavoitteen?

Toteutetaan se sitten:

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

Olisiko tämä tehokkaampaa?

3. Palauta k:s solmu viimeisestä

Haastattelukysymys 02.02. Palauta k:s solmu viimeisestä

Ensimmäinen asia, joka tulee mieleen tälle kysymykselle, on kulkea se kerran, jotta saadaan kokonaispituus, ja sitten löytää k:s solmu edellisestä kysymyksestä. Voit kuitenkin ajatella toista menetelmää edellisen kysymyksen perusteella: Samalla lailla,Nopeaa ja hidasta osoittimia käyttämällä anna nopea mennä k-1 solmulle ja sitten hidas ja nopea mennä samanaikaisesti on k:s solmu alhaalta.

Tämä kysymys osoittaa, että syöte k on laillinen, joten lisäarviointia ei tarvita, kuinka arvioida, onko k laiton, ja vaaditaan, että linkitetyn listan pituutta ei voida löytää suoraan, joten hitaan on arvioitava kävellessä.

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. Yhdistä linkitetyt luettelot

21. Yhdistä kaksi järjestettyä linkitettyä luetteloa

Idea:Sinun tarvitsee vain määrittää uusi solmu newH ja sitten verrata headA:n ja headB:n valuutta. Jotta voit lopulta löytää yhdistetyn linkitetyn luettelon pääsolmun, sinun on myös määritettävä tmp = newH ja sitten se, jolla on pienempi. tmp.next viittaa siihen.

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. Linkitetty luettelo jaettu

CM11 linkitetty luettelo jaettu

Tämä on haastattelukysymys Niukessa. Kysymyksen tarkoitus on jakaa linkitetty lista x:n vasen puoli on pienempi kuin x. Alkuperäistä järjestystä ei voi muuttaa.

Idea: Määritä uusi solmukäyrä, joka kulkee alkuperäisen linkitetyn luettelon läpi (jotta estät alkuperäisen linkitetyn luettelon muuttamisen), laita kaikki x:tä suuremmat asiat linkitettyyn luetteloon, lisää kaikki x:tä pienempi linkitettyyn luetteloon ja yhdistä lopuksi nämä kaksi. linkitetyt luettelot.

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

On huomattava, että jos ne ovat suurempia kuin x, eli bs = null, niin as palautetaan suoraan, ja jos as.next asetetaan lopulta tyhjäksi.

6. OR36 linkitetyn luettelon palindromirakenne

Linkitetyn luettelon OR36 palindromirakenne

Tämä on kysymys Niukelta, koska sillä on aikamonimutkaisuus ja tilan monimutkaisuusvaatimukset, mikä tarkoittaa, että et voi avata ylimääräistä taulukkoa, muuten avaruuden monimutkaisuus ei selviä ja normaalin läpikäynnin monimutkaisuus on O(n)

Idea on seuraava: etsi ensin linkitetyn listan keskisolmu ja sen jälkeen käännä osa keskeltä loppuun arvot ovat erilaisia, se tarkoittaa, että ne eivät palauta tekstirakennetta

Linkitetyn listan kääntämistä ja välisolmun löytämistä on harjoitettu aiemmin

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

On huomattava, että myös linkitetyn parittomien solmujen luettelon ja parillisten solmujen linkitetyn luettelon arvioinnissa on ero.

Jos parillinen solmu siirretään huipulle, se aiheuttaa äärettömän silmukan, joten parillisen solmun kohdalla tarvitaan lisäarviointia.

7. Leikkaavat linkitetyt luettelot

160. Leikkaavat linkitetyt luettelot

Leikkaava linkitetty lista on "Y":n kaltainen muunnos, kuten kuvassa näkyy

Myös alla olevan kysymyksen kuva on hyvin selkeä.

Idea: Koska onko A lyhyt tai B lyhyt, niiden välinen ero on leikkausta edeltävä osa. Sinun tarvitsee vain siirtää pitkää linkitettyä listaa, ja sitten kaksi linkitettyä listan solmua siirtyvät taaksepäin identtiset solmut leikkaavat solmun

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

Lopuksi meidän on lisättävä epäyhtenäinen tilanne. Vaikka voimme ohittaa tämän kysymyksen lisäämättä sitä, meidän on silti lisättävä se tarkkuuden vuoksi.

8. Pyöreä linkitetty luettelo

8.1 Selvitä, onko silmukkaa

141. Pyöreä linkitetty luettelo

Kuinka määrittää, onko linkitetyllä luettelolla sykli:Käytä silti nopeusosoitinta, aivan kuten kaksi ihmistä juoksee leikkikentällä, toinen juoksee nopeasti ja toinen juoksee hitaasti Koska leikkipaikka on rengas, nopea voi ehdottomasti ylittää hitaan , mutta ilman Tamakia, he eivät koskaan voisi tavata, aivan kuten jumalatar, jota et saa kiinni vaikka jahtaat kuinka lujasti.

Mutta on toinen tilanne, jos se on rengas, jossa on kaksi solmua ja määritetty nopea osoitin ottaa 3 askelta kerrallaan ja hidas osoitin 1 askeleen kerrallaan, ne eivät koskaan kohtaa.

Siksi määriteltyjen osoittimien on arvioitava, kuinka monta askelta he ottavat joka kerta. Jos toinen ottaa 2 askelta ja toinen 1 askeleen, ne kohtaavat varmasti.

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 Palauta solmu renkaan sisäänkäynnin kohdalla

142. Pyöreä linkitetty luettelo II

Tällä kertaa sinun on selvitettävä kehän sisääntulokohta sen jälkeen, kun olet päättänyt, onko se rengas edellisessä kysymyksessä. Voit tehdä seuraavan päättelyn

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

Mitä pitää lisätä, on:

Kun rengas on hyvin pieni, lopullinen yksinkertaistustulos tulee yllä olevaksi, mutta alkuperäinen koodi on edelleen kunnossa.