Wie man in Java auf einfache und optimale Weise den Schnittpunkt zweier einfach verknüpfter Listen findet

Um den Schnittpunkt zweier einfach verknüpfter Listen auf einfache und optimale Weise zu finden, können Sie den folgenden Ansatz verwenden. Die Schlüsselidee besteht darin, die Enden beider verknüpfter Listen auszurichten, indem der Startpunkt der längeren Liste angepasst wird, und dann beide Listen gleichzeitig zu durchlaufen, um den Schnittpunkt zu finden.

Schritte:

1. Längen berechnen: Berechnen Sie zunächst die Längen beider verknüpfter Listen.
2. Startzeiger ausrichten: Wenn eine Liste länger als die andere ist, verschieben Sie den Zeiger, um die Längen beider Listen auszurichten.
3. Schnittpunkt finden: Beide Listen gleichzeitig durchqueren. Der erste Knoten, an dem sie sich treffen, ist der Schnittpunkt.

Java-Implementierung:

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.");
        }
    }
}

Erläuterung:

1. ListNode-Klasse:

   • Stellt jeden Knoten in der verknüpften Liste mit einem Wert (val) und einem Zeiger auf den nächsten Knoten (next) dar.

2. getIntersectionNode-Methode:

   • Längen berechnen: Die Längen beider verknüpfter Listen werden mit der getLength-Methode berechnet.
   • Startzeiger ausrichten: Wenn die Listen unterschiedliche Längen haben, wird der Zeiger der längeren Liste vorgerückt, um ihn am Zeiger der kürzeren Liste auszurichten.
   • Gemeinsam verfahren: Beide Zeiger werden dann gleichzeitig bewegt. Der erste Knoten, an dem sie übereinstimmen, ist der Schnittpunkt.

3. getLength-Methode:

   • Eine Hilfsmethode zur Berechnung der Länge einer verknüpften Liste.

4. printList-Methode:

   • Eine Hilfsfunktion zum Drucken der Knoten der verknüpften Liste.

5. Hauptmethode:

   • Erstellen Sie zwei verknüpfte Listen: Zum Beispiel 1 -> 3 -> 5 -> 7 -> 9 -> 11 und 2 -> 4 -> 9 -> 11, wo der Schnittpunkt bei Knoten 9 beginnt.
   • Suchen und drucken Sie den Schnittpunkt: Das Programm gibt 9 als Schnittpunkt aus.

Komplexität:

• Zeitkomplexität: ( O(m + n) ), wobei ( m ) und ( n ) die Längen der beiden verknüpften Listen sind. Die Listen werden maximal zweimal durchlaufen.
• Raumkomplexität: ( O(1) ), da nur wenige zusätzliche Zeiger verwendet werden.

Diese Methode ist einfach und optimal und stellt sicher, dass Sie den Schnittpunkt zweier einfach verknüpfter Listen auf effiziente Weise finden.

Das obige ist der detaillierte Inhalt vonWie man in Java auf einfache und optimale Weise den Schnittpunkt zweier einfach verknüpfter Listen findet. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!