Exemple d'analyse de liste chaînée Java

1. Supprimez tous les nœuds avec la valeur val

Supprimez tous les nœuds de la liste chaînée qui sont égaux à la valeur val donnée. [Lien JO]

Définissez deux pointeurs prev et cur, cur pointe vers le nœud suivant du nœud principal et prev pointe toujours vers le nœud précédent de cur (pratique pour supprimer des nœuds). Utilisez le pointeur cur pour parcourir la liste chaînée et comparez-la avec la valeur val Si elle est la même, supprimez le nœud. Enfin, comparez les nœuds principaux.

/**
 * 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. Inversez la liste chaînée

Inversez une liste chaînée. [Lien JO]

Lorsque vous parcourez la liste chaînée, modifiez le pointeur du nœud actuel pour qu'il pointe vers le nœud précédent. Puisqu’un nœud n’a pas de référence à son nœud précédent, son nœud précédent doit être stocké au préalable. Ce dernier nœud doit également être stocké avant de changer la référence. Enfin, la nouvelle référence d'en-tête est renvoyée.

/**
 * 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. Renvoie le nœud central de la liste chaînée

Étant donné une liste chaînée non vide avec un nœud principal, renvoie le nœud central de la liste chaînée. S'il y a deux nœuds intermédiaires, le deuxième nœud intermédiaire est renvoyé. [Lien JO]

Nous pouvons définir deux pointeurs rapides et lents (rapide, lent), tous deux pointant vers le nœud principal. Le pointeur rapide fait deux pas à la fois et le pointeur lent fait un pas à la fois. Lorsque la liste chaînée a un nombre pair de nœuds, slow est le nœud intermédiaire lorsque fast=null ; lorsque la liste chaînée a un nombre impair de nœuds, slow est le nœud intermédiaire lorsque fast.next=null.

/**
 * 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. Renvoyez le Kème nœud de la liste chaînée

Entrez une liste chaînée et renvoyez le Kème nœud du bas dans la liste chaînée. [Lien JO]

Cette question s'apparente à l'idée de trouver le nœud du milieu. Définissez deux pointeurs (rapide, lent). En partant du principe que K est raisonnable, nous pouvons laisser le pointeur rapide parcourir les étapes K-1 en premier, puis les pointeurs rapide et lent reculer en même temps. Lorsque fast atteint la fin de la liste chaînée, slow pointe vers le K. -ème nœud à partir du bas.

/*
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. Fusionner les listes chaînées ordonnées

Fusionnez deux listes chaînées ordonnées en une seule liste chaînée ordonnée et revenez. La nouvelle liste chaînée est formée en concaténant tous les nœuds des deux listes chaînées données. [Lien JO]

Pour résoudre ce problème, vous devez définir un faux nœud qui servira de nœud principal de la nouvelle liste chaînée. Parcourez les deux nœuds à travers les nœuds principaux des deux listes liées, comparez les valeurs des nœuds correspondants des deux listes liées et connectez le nœud avec la valeur la plus petite à l'arrière de la nouvelle liste liée. les listes sont parcourues, lorsqu'une des listes chaînées est vide, connectez simplement une autre liste chaînée directement à l'arrière de la nouvelle liste chaînée.

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. Divisez la liste chaînée par valeur

Divisez une liste chaînée en deux parties selon une valeur X donnée, et tous les nœuds inférieurs à X sont classés avant les nœuds supérieurs ou égaux à X. L'ordre initial des nœuds n'est pas modifié. [Lien JO]

Nous devons d'abord définir quatre pointeurs (bs, be, as, ae) pour représenter respectivement le nœud de tête et le nœud de queue de la liste chaînée plus petits que X, et le nœud de tête et le nœud de queue de la liste chaînée plus grand que X. Parcourez la liste chaînée via le nœud principal et divisez la liste chaînée en deux parties. Enfin, connectez les deux listes chaînées. Une attention particulière doit être accordée au fait que lorsque la liste chaînée inférieure à X n'est pas vide, nous devons définir manuellement ae.next sur vide.

/*
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. Interpréter la liste chaînée palindrome

Déterminez si la liste chaînée est une liste chaînée palindrome. [Lien JO]

Nous devons d'abord trouver le nœud central de la liste chaînée, puis inverser la seconde moitié de la liste chaînée. Enfin, comparez simplement étape par étape les deux côtés. Faites particulièrement attention au fait que lorsque le nombre de nœuds dans la liste chaînée est un nombre pair, en raison des nœuds intermédiaires, les deux côtés ne peuvent pas se rencontrer lors de la traversée et un traitement spécial est requis.

/*
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. Trouvez le nœud commun des deux listes liées

Entrez les deux listes liées et affichez le premier nœud commun des deux listes liées. Aucun NULL n'est renvoyé. [Lien JO]

L'intersection de deux listes chaînées présente une forme en Y. Ensuite, la différence de longueur des deux listes chaînées doit être la différence entre les deux nœuds de la liste chaînée avant leur intersection. Nous devons trouver la longueur des deux listes chaînées. Définissez deux pointeurs (pl, ps), laissez pl pointer vers la longue liste chaînée et ps pointer vers la courte liste chaînée. Trouvez la différence de longueur len entre les deux listes chaînées. Donnez-leur envie de prendre des mesures. De cette façon, les longueurs restantes des deux listes chaînées sont les mêmes. A ce moment, les deux pointeurs parcourent deux listes chaînées en même temps. S'ils pointent vers le même point, les deux listes chaînées se croisent. Sinon, les deux listes chaînées ne se croisent pas.

/**
 * 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. Déterminez s'il y a une bague dans la liste chaînée

. [Lien JO]

Toujours un indicateur de vitesse. Le pointeur lent fait un pas à la fois et le pointeur rapide fait deux pas à la fois. Les deux pointeurs commencent au début de la liste chaînée. Si la liste chaînée a un anneau, ils se rencontreront certainement dans l'anneau, sinon le pointeur rapide atteindra en premier la fin de la liste chaînée.

/**
 * 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. Renvoyez l'entrée de la liste chaînée en anneau

Étant donné une liste chaînée, déterminez s'il y a un anneau dans la liste chaînée et renvoyez le nœud entrant dans l'anneau. S'il n'y a pas de cycle, NULL est renvoyé. 【Lien JO】

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

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!