Technologieaustausch

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

💎 欢迎各位大佬互三：Meine Homepage

1. Umgekehrte verknüpfte Liste

206.Umgekehrt verknüpfte Liste

Überlegung: Welche Methode sollte verwendet werden, wenn Sie keinen zusätzlichen Speicherplatz freigeben und nur die ursprüngliche verknüpfte Liste ändern?

Beginnen Sie einfach mit dem zweiten Element und führen Sie das Einfügen des Kopfes nacheinander durch.

Ändern Sie dann einfach die Referenz und zeigen Sie das letzte Element auf 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. Der mittlere Knoten der verknüpften Liste

876. Zwischenknoten der verknüpften Liste

Die erste Methode, die mir für diese Frage in den Sinn kommt, besteht definitiv darin, einen cnt zu definieren, die verknüpfte Liste einmal zu durchlaufen, dann die mittlere Zahl zu finden und dann den Rückgabewert zu durchlaufen. Diese Methode ist sehr einfach, aber was ist, wenn Sie die durchlaufen müssen? Verknüpfte Liste nur einmal, um den Zwischenknoten zu finden?

Hier ist eine neue Idee: Verwenden Sie die schnellen und langsamen Zeiger, beginnend mit dem Kopf. Der schnelle Zeiger bewegt sich jedes Mal um zwei Knoten, und der langsame Zeiger bewegt sich jedes Mal um einen Knoten.

Dann lass es uns umsetzen:

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

Wäre das effizienter?

3. Geben Sie den k-ten Knoten vom letzten zurück

Interviewfrage 02.02. Geben Sie den k-ten Knoten vom letzten zurück

Das erste, was mir bei dieser Frage in den Sinn kommt, ist, sie einmal zu durchlaufen, um die Gesamtlänge zu erhalten, und dann den k-ten Knoten vom letzten zu finden. Auf der Grundlage der vorherigen Frage können Sie sich jedoch eine andere Methode vorstellen: Ähnlich,Verwenden Sie die Zeiger „Fast“ und „Slow“, um zuerst die Knoten „Fast“ und „Fast“ gleichzeitig zu durchlaufen ist der k-te Knoten von unten.

Diese Frage zeigt an, dass die Eingabe k zulässig ist, sodass keine zusätzliche Beurteilung erforderlich ist. So beurteilen Sie, ob k illegal ist, und es ist erforderlich, dass die Länge der verknüpften Liste nicht direkt ermittelt werden kann, sodass eine langsame Beurteilung beim Gehen erforderlich ist.

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. Verknüpfte Listen zusammenführen

21. Führen Sie zwei geordnete verknüpfte Listen zusammen

Idee:Sie müssen nur einen neuen Knoten newH definieren und dann den Wert von headA und headB vergleichen. Um schließlich den Kopfknoten der zusammengeführten verknüpften Liste zu finden, müssen Sie auch einen tmp = newH definieren und dann denjenigen, der den kleineren hat tmp.next zeigt darauf.

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. Aufteilung der verknüpften Liste

Aufteilung der verknüpften CM11-Liste

Dies ist eine Interviewfrage zu Niuke. Die linke Seite von x ist kleiner als x und die rechte Seite ist größer als x.

Idee: Definieren Sie einen neuen Knotencur, um die ursprüngliche verknüpfte Liste zu durchlaufen (um zu verhindern, dass die ursprüngliche verknüpfte Liste geändert wird), fügen Sie alles, was größer als x ist, in eine verknüpfte Liste ein, fügen Sie alles, was kleiner als x ist, in eine verknüpfte Liste ein und verbinden Sie schließlich die beiden verknüpfte Listen.

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

Es ist zu beachten, dass, wenn sie größer als x sind, also bs = null, as direkt zurückgegeben wird und as.next schließlich auf null gesetzt wird

6. Palindromstruktur der verknüpften OR36-Liste

OR36-Palindromstruktur der verknüpften Liste

Dies ist eine Frage von Niuke, da es Anforderungen an Zeitkomplexität und Raumkomplexität gibt, was bedeutet, dass Sie kein zusätzliches Array öffnen können, da sonst die Raumkomplexität nicht überwunden wird und die normale Durchquerung eine Komplexität von O(n) hat.

Die Idee ist wie folgt: Suchen Sie zuerst den langsamen Mittelknoten der verknüpften Liste und kehren Sie dann den Kopfknoten rückwärts und den langsamen Knoten zurück Die Werte sind unterschiedlich, das bedeutet, dass sie keine Textstruktur zurückgeben

Das Umkehren der verknüpften Liste und das Finden des Zwischenknotens wurden bereits zuvor geübt

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

Es ist zu beachten, dass es auch einen Unterschied in der Beurteilung der verknüpften Liste ungeradzahliger Knoten und der verknüpften Liste geradzahliger Knoten gibt.

Wenn der Knoten mit der geraden Nummer nach oben verschoben wird, führt dies zu einer Endlosschleife, sodass für den Knoten mit der geraden Nummer eine zusätzliche Beurteilung erforderlich ist.

7. Überschnittene verknüpfte Listen

160. Überschnittene verknüpfte Listen

Die sich überschneidende verknüpfte Liste ist eine Transformation ähnlich „Y“, wie in der Abbildung gezeigt

Das Bild in der Frage unten ist auch sehr klar.

Idee: Denn unabhängig davon, ob A kurz oder B kurz ist, ist der Unterschied zwischen ihnen der Teil vor dem Schnittpunkt. Sie müssen die lange verknüpfte Liste nur um einen Unterschied verschieben, und dann werden die beiden verknüpften Listenknoten gleichzeitig rückwärts verschoben Identische Knoten sollen sich schneiden

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

Schließlich müssen wir die disjunkte Situation hinzufügen. Obwohl wir diese Frage bestehen können, ohne sie hinzuzufügen, müssen wir sie der Genauigkeit halber dennoch hinzufügen.

8. Zirkuläre verknüpfte Liste

8.1 Bestimmen Sie, ob eine Schleife vorhanden ist

141. Zirkuläre verknüpfte Liste

So ermitteln Sie, ob eine verknüpfte Liste einen Zyklus hat:Benutzen Sie immer noch den Geschwindigkeitszeiger, genau wie zwei Leute, die auf dem Spielplatz laufen, eine Person läuft schnell und die andere Person läuft langsam. Da der Spielplatz ein Ring ist, kann der Schnelle den Langsamen definitiv übertreffen. Zu diesem Zeitpunkt trafen sie sich , aber ohne Tamaki könnten sie sich nie treffen, genau wie eine Göttin, die man nicht fangen kann, egal wie sehr man sie jagt.

Aber es gibt noch eine andere Situation: Wenn es sich um einen Ring mit zwei Knoten handelt und der definierte schnelle Zeiger jeweils drei Schritte und der langsame Zeiger jeweils einen Schritt ausführt, werden sie sich nie treffen.

Daher müssen die definierten Zeiger beurteilen, wie viele Schritte sie jedes Mal machen. Wenn einer zwei Schritte macht und der andere einen Schritt macht, werden sie sich definitiv treffen.

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 Bringen Sie den Knoten am Ringeingang zurück

142. Zirkuläre verlinkte Liste II

Dieses Mal müssen Sie den Eintrittspunkt in den Ring herausfinden, nachdem Sie in der vorherigen Frage beurteilt haben, ob es sich um einen Ring handelt. Sie können die folgende Überlegung anstellen

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

Was hinzugefügt werden muss, ist:

Wenn der Ring sehr klein ist, sieht das endgültige Vereinfachungsergebnis wie oben aus, aber der ursprüngliche Code ist immer noch in Ordnung.