Beispielanalyse einer Java-verknüpften Liste

1. Alle Knoten mit dem Wert val löschen.

Alle Knoten in der verknüpften Liste löschen, die dem angegebenen Wert val entsprechen. [OJ-Link]

Definieren Sie zwei Zeiger prev und cur, cur zeigt auf den nächsten Knoten des Kopfknotens und prev zeigt immer auf den vorherigen Knoten von cur (praktisch zum Löschen von Knoten). Verwenden Sie den Cur-Zeiger, um die verknüpfte Liste zu durchlaufen und sie mit dem Val-Wert zu vergleichen. Wenn er identisch ist, löschen Sie den Knoten. Vergleichen Sie abschließend die Kopfknoten.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head==null){
            return null;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(cur.val==val){
                prev.next=cur.next;
                cur=cur.next;
            }else{
                prev=cur;
                cur=cur.next;
            }
        }
        if(head.val==val){
            head=head.next;
        }
        return head;
    }
}

2. Die verknüpfte Liste umkehren

Eine verknüpfte Liste umkehren. [OJ-Link]

Ändern Sie beim Durchlaufen der verknüpften Liste den Zeiger des aktuellen Knotens so, dass er auf den vorherigen Knoten zeigt. Da ein Knoten keinen Bezug zu seinem Vorgängerknoten hat, muss sein Vorgängerknoten vorher gespeichert werden. Der letztgenannte Knoten muss ebenfalls gespeichert werden, bevor die Referenz geändert wird. Abschließend wird die neue Header-Referenz zurückgegeben.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=head;
            head=cur;
            cur=curNext;
        }
        return head;
    }
}

3. Geben Sie den mittleren Knoten der verknüpften Liste zurück. Geben Sie bei einer nicht leeren einfach verknüpften Liste mit einem Kopfknoten den mittleren Knoten der verknüpften Liste zurück. Bei zwei Zwischenknoten wird der zweite Zwischenknoten zurückgegeben. [OJ-Link]

Wir können zwei schnelle und langsame Zeiger (schnell, langsam) definieren, die beide auf den Kopfknoten zeigen. Der schnelle Zeiger führt jeweils zwei Schritte aus, während der langsame Zeiger jeweils einen Schritt ausführt. Wenn die verknüpfte Liste eine gerade Anzahl von Knoten hat, ist „slow“ der Zwischenknoten, wenn fast.next=null ist; wenn die verknüpfte Liste eine ungerade Anzahl von Knoten hat, ist „slow“ der Zwischenknoten, wenn fast.next=null ist.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

4. Geben Sie den K-ten Knoten der verknüpften Liste zurück. Geben Sie eine verknüpfte Liste ein und geben Sie den K-ten Knoten von unten in der verknüpften Liste zurück. [OJ-Link]

Diese Frage ähnelt der Idee, den mittleren Knoten zu finden. Definieren Sie zwei Zeiger (schnell, langsam). Unter der Voraussetzung, dass K sinnvoll ist, können wir den schnellen Zeiger zuerst K-1 Schritte gehen lassen und dann den schnellen und den langsamen Zeiger gleichzeitig rückwärts bewegen. Wenn der schnelle Zeiger das Ende der verknüpften Liste erreicht, zeigt der langsame Zeiger auf den K -ter Knoten von unten.

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
        if(k<=0||head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(k-1>0){
            if(fast.next==null){
                return null;
            }
            fast=fast.next;
            //先让快节点走k-1步
            k--;
        }
        while(fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
       
    }
}

5. Geordnete verknüpfte Listen zusammenführen

Fügen Sie zwei geordnete verknüpfte Listen zu einer geordneten verknüpften Liste zusammen und kehren Sie zurück. Die neue verknüpfte Liste wird durch Verketten aller Knoten der beiden angegebenen verknüpften Listen gebildet. [OJ Link]

Um dieses Problem zu lösen, müssen Sie einen falschen Knoten definieren, der als Kopfknoten der neuen verknüpften Liste dient. Durchlaufen Sie die beiden Knoten durch die Kopfknoten der beiden verknüpften Listen, vergleichen Sie die Werte der entsprechenden Knoten der beiden verknüpften Listen und verbinden Sie den Knoten mit dem kleineren Wert mit der Rückseite der neuen verknüpften Liste Listen werden durchlaufen, wenn eine der verknüpften Listen leer ist. Verbinden Sie einfach eine andere verknüpfte Liste direkt mit der Rückseite der neuen verknüpften Liste.

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        //创建虚拟节点，充当新链表的头节点，值不代表任何意义
        ListNode node=new ListNode(-1);
        ListNode cur=node;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                cur.next=list1;
                list1=list1.next;
            }else{
                cur.next=list2;
                list2=list2.next;
            }
            cur=cur.next;
        }
        if(list1==null){
            cur.next=list2;
        }else{
            cur.next=list1;
        }
        return node.next;
    }
}

6. Teilen Sie die verknüpfte Liste nach Wert auf. Teilen Sie eine verknüpfte Liste entsprechend einem bestimmten Wert X in zwei Teile. Alle Knoten, die kleiner als X sind, werden vor Knoten größer oder gleich X eingestuft. Die ursprüngliche Reihenfolge der Knoten wird nicht geändert. [OJ-Link]

Zuerst müssen wir vier Zeiger (bs, be, as, ae) definieren, um jeweils den Kopfknoten und den Endknoten der verknüpften Liste kleiner als X sowie den Kopfknoten und den Endknoten der verknüpften Liste darzustellen größer als X. Durchlaufen Sie die verknüpfte Liste durch den Kopfknoten und teilen Sie die verknüpfte Liste in zwei Teile. Verbinden Sie abschließend die beiden verknüpften Listen. Besonderes Augenmerk sollte darauf gelegt werden, dass wir ae.next manuell auf leer setzen müssen, wenn die verknüpfte Liste kleiner als X nicht leer ist.

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        if(pHead==null){
            return null;
        }
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;
        ListNode cur=pHead;
        while(cur!=null){
            if(cur.val<x){
                if(bs==null){
                    bs=cur;
                    be=cur;
                }else{
                    be.next=cur;
                    be=cur;
                }
            }else{
                if(as==null){
                    as=cur;
                    ae=cur;
                }else{
                    ae.next=cur;
                    ae=cur;
                }
            }
            cur=cur.next;
        }
        if(bs==null){
            return as;
            //如果小于X部分为空，则直接返回大于X部分即可。此时ae.next一定为null
        }
        be.next=as;//否则连接小于X和大于X部分
        if(as!=null){
           ae.next=null;
           //当小于X部分不为空时，ae.next可能不为null，需要手动置为null
        }
        return bs;
    }
}

7. Interpretieren Sie die verknüpfte Palindrom-Liste. Bestimmen Sie, ob es sich bei der verknüpften Liste um eine verknüpfte Palindrom-Liste handelt. [OJ-Link]

Zuerst müssen wir den mittleren Knoten der verknüpften Liste finden und dann die zweite Hälfte der verknüpften Liste umkehren. Vergleichen Sie abschließend einfach Schritt für Schritt beide Seiten. Achten Sie besonders darauf, dass sich die beiden Seiten beim Durchlaufen aufgrund der Zwischenknoten nicht treffen können und eine spezielle Verarbeitung erforderlich ist, wenn die Anzahl der Knoten in der verknüpften Liste eine gerade Zahl ist.

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        if(A==null){
            return false;
        }
        if(A.next==null){
            return true;
        }
        //求链表的中间节点
        ListNode slow=A;
        ListNode fast=A;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反转后半段链表
        ListNode cur=slow.next;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curNext;
        }
        //判断回文链表
        while(slow!=A){
            if(slow.val!=A.val){
              return false;
           }
            if(A.next==slow){
                return true;
            }
            slow=slow.next;
            A=A.next;
        }
        return true;
    }
}

8. Finden Sie den gemeinsamen Knoten der beiden verknüpften Listen.

Geben Sie die beiden verknüpften Listen ein und geben Sie den ersten gemeinsamen Knoten der beiden verknüpften Listen aus. Es wird kein NULL zurückgegeben. [OJ-Link]

Der Schnittpunkt zweier verknüpfter Listen weist eine Y-Form auf. Dann muss der Längenunterschied der beiden verknüpften Listen dem Unterschied zwischen den beiden verknüpften Listenknoten entsprechen, bevor sie sich schneiden. Wir müssen die Länge der beiden verknüpften Listen ermitteln. Definieren Sie zwei Zeiger (pl, ps), lassen Sie pl auf die lange verknüpfte Liste zeigen und ps auf die kurze verknüpfte Liste. Finden Sie den Längenunterschied len zwischen den beiden verknüpften Listen. Machen Sie Lust, lange Schritte zu unternehmen. Auf diese Weise sind die verbleibenden Längen der beiden verknüpften Listen gleich. Zu diesem Zeitpunkt durchlaufen die beiden Zeiger gleichzeitig zwei verknüpfte Listen. Wenn sie auf denselben Punkt zeigen, überschneiden sich die beiden verknüpften Listen.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //求链表长度
    public int len(ListNode head){
        int len=0;
        while(head!=null){
            head=head.next;
            len++;
        }
        return len;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null||headB==null){
            return null;
        }
        ListNode pl=headA;
        ListNode ps=headB;
        int lenA=len(headA);
        int lenB=len(headB);
        int len=lenA-lenB;
        if(len<0){
            //pl指向长的链表，ps指向短的链表
            pl=headB;
            ps=headA;
            len=-len;
        }
        while(len--!=0){
            pl=pl.next;
        }
        while(pl!=null){
            if(pl==ps){
                return pl;
            }
            pl=pl.next;
            ps=ps.next;
        }
        return null;
    }
}

9. Stellen Sie fest, ob in der verknüpften Liste ein Ring vorhanden ist

. [OJ-Link]

Immer noch ein Geschwindigkeitszeiger. Der langsame Zeiger macht einen Schritt nach dem anderen und der schnelle Zeiger macht zwei Schritte nach dem anderen. Die beiden Zeiger beginnen am Anfang der verknüpften Liste. Wenn die verknüpfte Liste einen Ring hat, treffen sie sich definitiv im Ring, andernfalls erreicht der schnelle Zeiger zuerst das Ende der verknüpften Liste.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null){
            return false;//链表为空或者只有一个节点时，没有环
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
                //如果快慢节点可以相遇，表示链表有环
            }
        }
        return false;
    }
}

10. Geben Sie den Eintrag der verknüpften Ringliste zurück. Bestimmen Sie anhand einer verknüpften Liste, ob ein Ring in der verknüpften Liste vorhanden ist, und geben Sie den Knoten zurück, der in den Ring eintritt. Wenn kein Zyklus vorhanden ist, wird NULL zurückgegeben. 【ABl.-Link】

让一个指针从链表的其实在位置开始遍历，同时另一个指针从上题中两只真相与的位置开始走，两个指针再次相遇时的位置肯定为环的入口

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    //判断链表是否有环，并返回第一次快慢节点相交的位置
    public ListNode hasCycle(ListNode head){
         if(head==null||head.next==null){
            return null;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
               return slow;
            }
        }
        return null;
    }
    //当返回的结点与头节点再次相交时，为环的入口
    public ListNode detectCycle(ListNode head) {
        ListNode node=hasCycle(head);
        if(node==null){
            return null;
        }else{
            while(head!=node){
                head=head.next;
                node=node.next;
            }
        }
        return head;
    }
}

Das obige ist der detaillierte Inhalt vonBeispielanalyse einer Java-verknüpften Liste. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!