Algorithmusgymnastik 12

Intersection Point of Two Lists

Erläuterung

Die Köpfe der beiden verknüpften Listen werden übergeben. Stellen Sie also fest, ob sich die beiden verknüpften Listen tatsächlich überschneiden. Implementieren wir einen Algorithmus, der diesen Schnittpunkt zurückgibt. Gibt null zurück, wenn keine Schnittpunkte vorhanden sind. Eine Kreuzung zu sein bedeutet, dass die Knoten dieselbe speicherinterne Adresse haben.

Im folgenden Beispiel schneidet sich keine Liste. Im folgenden Beispiel gibt es einen Knoten, der 12 Daten an der Kreuzung enthält, sodass der Knoten zurückgegeben wird.

Solution1 Die erste Implementierungsmethode, die in den Sinn kommt, ist zunächst, ob der Knoten der ersten verknüpften Liste auch in der zweiten verknüpften Liste vorhanden ist. Ein ineffizienter Algorithmus mit einer Ausführungszeit von O (m * n) (m und n sind die Längen der verknüpften Liste). In diesem Fall ist die Ausführungszeit langsam, aber die Raumkomplexität ist O (1), da nur mit zwei Zeigern gescannt wird.

Solution2 Angenommen, Sie haben viel Speicher und möchten Ihre Ausführungszeit effizienter verbessern. In diesem Fall fällt mir als Erstes ein Es wird eine Datenstruktur verwendet, die HashTable verwendet. Daher werden wir es mit Javas HashSet implementieren. Fügen Sie zunächst Knoten zum Hash-Set hinzu, während Sie die Elemente einer verknüpften Liste linear scannen. Überprüfen Sie anschließend, ob derselbe Knoten im Hash-Set vorhanden ist, während Sie die zweite verknüpfte Liste linear durchsuchen. Da der Zugriff auf die Elemente von HashSet natürlich O (1) ist, beträgt die Ausführungszeit dieser Implementierung O (m + n), was effizienter ist.

Implementierung

Intersect.java

class Intersect{
  public LinkedListNode findintersect(LinkedListNode head1,LinkedListNode head2) {

    LinkedListNode cur1 = head1;
    LinkedListNode cur2 = head2;
    LinkedListNode interSectionNode = null;
    HashSet<LinkedListNode> hashSet = new HashSet<>();

    while (cur1 != null) {
      hashSet.add(cur1);
      cur1 = cur1.next;
    }

    while (cur2 != null) {
      if (hashSet.contains(cur2)) {
        interSectionNode = cur2;
        break;
      }
      cur2 = cur2.next;
    }

    return interSectionNode;
  } 
}

Solution3 Nehmen wir nun an, dass die verknüpfte Liste eine große Datenmenge enthält, und überlegen wir, ob wir die Speichereffizienz ein wenig weiter verbessern können. Nehmen wir zunächst an, dass beide verknüpften Listen dieselbe Größe haben. In diesem Fall können Sie die Adressen von Knoten mit zwei verschiedenen Zeigern vom Anfang beider vergleichen. Wenn diese Adressen übereinstimmen, bedeutet dies, dass es sich um eine Kreuzung handelt. Wenn sie nicht übereinstimmen, stellen Sie beide Zeiger ** gleichzeitig ** um eins vor, um die Adressen zu vergleichen. Wiederholen Sie diesen Vorgang, bis Sie eine Kreuzung finden oder beide Listen verschwunden sind. Wenn die Listenlängen unterschiedlich sind, verwenden wir dieses Konzept für das Problem.

1. Ermitteln Sie die Längen der beiden verknüpften Listen: L1 und L2. 2.Berechnen Sie den Längenunterschied zwischen L1 und L2. d= | L1-L2 |
2. Bewegen Sie den Zeiger vom Kopf um die Differenz von "d" zur längeren Liste.
3. Jetzt entspricht die Länge der Liste vom verschobenen Zeiger der Länge der anderen Liste.
4. Scannen Sie beide Listen und vergleichen Sie die Knoten, bis die Adressen übereinstimmen oder die Liste das Ende erreicht.

Mit diesem Algorithmus bleibt die Ausführungszeit O (n + m) und die Speichereffizienz kann O (1) sein.

Beispiel

Implementierung

Intersect.java

class Intersect{
  public LinkedListNode findIntersect(LinkedListNode head1,LinkedListNode head2) {

    LinkedListNode list1node = null;
    int list1length = getLength(head1);
    LinkedListNode list2node = null;
    int list2length = getLength(head2);

    int length_difference = 0;
    if(list1length >= list2length) {
      length_difference = list1length - list2length;
      list1node = head1;
      list2node = head2;
    } else {
      length_difference = list2length - list1length;
      list1node = head2;
      list2node = head1;
    }

    while(length_difference > 0) {
      list1node = list1node.next;
      length_difference--;
    }

    while(list1node != null) {
      if(list1node == list2node) {
        return list1node;
      }

      list1node = list1node.next;
      list2node = list2node.next;
    }
    return null;
  }

  private int getLength(
    LinkedListNode head) {      
    int list_length = 0;
    while(head != null) {
      head = head.next;
      list_length++;
    }
    return list_length;
  }
}