Comment trouver l'intersection de deux listes chaînées de manière simple et optimale en Java

Pour trouver l'intersection de deux listes chaînées de manière simple et optimale, vous pouvez utiliser l'approche suivante. L'idée clé est d'aligner les extrémités des deux listes chaînées en ajustant le point de départ de la liste la plus longue, puis de parcourir les deux listes simultanément pour trouver le point d'intersection.

Mesures:

1. Calculer les longueurs : Tout d'abord, calculez les longueurs des deux listes chaînées.
2. Aligner les pointeurs de début : Si une liste est plus longue que l'autre, avancez son pointeur pour aligner les longueurs des deux listes.
3. Trouver une intersection : parcourez les deux listes simultanément. Le premier nœud où ils se rencontrent est le point d'intersection.

Implémentation Java :

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class LinkedList {

    // Function to get the intersection node of two linked lists
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // Calculate the lengths of both linked lists
        int lengthA = getLength(headA);
        int lengthB = getLength(headB);

        // Align the start of both lists
        while (lengthA > lengthB) {
            headA = headA.next;
            lengthA--;
        }

        while (lengthB > lengthA) {
            headB = headB.next;
            lengthB--;
        }

        // Traverse both lists together to find the intersection
        while (headA != headB) {
            headA = headA.next;
            headB = headB.next;
        }

        return headA;  // or headB, they are the same at intersection point
    }

    // Utility function to calculate the length of a linked list
    private int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    // Function to print the linked list
    public void printList(ListNode head) {
        ListNode temp = head;
        while (temp != null) {
            System.out.print(temp.val + " ");
            temp = temp.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Create two linked lists
        // List A: 1 -> 3 -> 5 -> 7 -> 9 -> 11
        ListNode headA = new ListNode(1);
        headA.next = new ListNode(3);
        headA.next.next = new ListNode(5);
        headA.next.next.next = new ListNode(7);
        headA.next.next.next.next = new ListNode(9);
        headA.next.next.next.next.next = new ListNode(11);

        // List B: 2 -> 4 -> 9 -> 11
        ListNode headB = new ListNode(2);
        headB.next = new ListNode(4);
        headB.next.next = headA.next.next.next.next;  // 9
        headB.next.next.next = headA.next.next.next.next.next;  // 11

        System.out.println("List A:");
        list.printList(headA);

        System.out.println("List B:");
        list.printList(headB);

        // Find intersection
        ListNode intersection = list.getIntersectionNode(headA, headB);

        if (intersection != null) {
            System.out.println("Intersection at node with value: " + intersection.val);
        } else {
            System.out.println("No intersection.");
        }
    }
}

Explication:

1. Classe ListNode :

   • Représente chaque nœud de la liste chaînée avec une valeur (val) et un pointeur vers le nœud suivant (next).

2. Méthode getIntersectionNode :

   • Calculer les longueurs : Les longueurs des deux listes chaînées sont calculées à l'aide de la méthode getLength.
   • Aligner les pointeurs de début : Si les listes ont des longueurs différentes, le pointeur de la liste la plus longue est avancé pour s'aligner avec le pointeur de la liste la plus courte.
   • Traverse Together : Les deux pointeurs sont ensuite déplacés simultanément. Le premier nœud où ils correspondent est le nœud d'intersection.

3. Méthode getLength :

   • Une méthode d'assistance pour calculer la longueur d'une liste chaînée.

4. Méthode printList :

   • Une fonction utilitaire pour imprimer les nœuds de la liste chaînée.

5. Méthode principale :

   • Créez deux listes chaînées : Par exemple, 1 -> 3 -> 5 -> 7 -> 9 -> 11 et 2 -> 4 -> 9 -> 11, où l'intersection commence au nœud 9.
   • Trouver et imprimer l'intersection : Le programme affichera 9 comme point d'intersection.

Complexité:

• Complexité temporelle : ( O(m + n) ), où ( m ) et ( n ) sont les longueurs des deux listes chaînées. Les listes sont parcourues au maximum deux fois.
• Complexité spatiale : ( O(1) ), puisque seuls quelques pointeurs supplémentaires sont utilisés.

Cette méthode est simple et optimale, garantissant que vous trouvez le point d'intersection de deux listes chaînées de manière efficace.

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!