Java implementiert die gemeinsame Nutzung von Kopiercode für komplexe verknüpfte Listen

In diesem Artikel wird hauptsächlich die Java-Interviewfrage vorgestellt – das Teilen des Kopiercodes zum Implementieren einer komplexen verknüpften Liste. Der Herausgeber findet es ziemlich gut und hat einen Referenzwert.

Abschließende Fragen zur Online-Programmierung von Alibaba, schreiben Sie sie auf und teilen Sie sie mit allen

Es gibt eine einseitig verknüpfte Liste. Jeder Knoten enthält einen zufälligen Zeiger, der auf einen Knoten in dieser verknüpften Liste zeigt oder auf „Leer“ schreiben Sie eine Deep-Copy-Funktion, um die gesamte verknüpfte Liste einschließlich des Zufallszeigers zu kopieren. Berücksichtigen Sie nach Möglichkeit mögliche Ausnahmen.

Der Algorithmus ist wie folgt:

/*
public class RandomListNode {
  int label;
  RandomListNode next = null;
  RandomListNode random = null;
  RandomListNode(int label) {
    this.label = label;
  }
}
*/
public class Solution {
  public RandomListNode Clone(RandomListNode pHead)
  {
    copyNodes(pHead);
    setClonedNodes(pHead);
    return splitNodes(pHead);
  }
    //第一步，复制链表任意结点N并创建新结点N‘，再把N'链接到N的后面
   public static void copyNodes(RandomListNode head){ 
    RandomListNode temp = head;
    while(temp!=null){
     RandomListNode clonedNode = new RandomListNode(0);
     clonedNode.next = temp.next;
     clonedNode.label = temp.label;
     clonedNode.random = null;
     temp.next = clonedNode;
     temp = clonedNode.next;
    }
   }
   //第二步，设置复制出来的结点
   public static void setClonedNodes(RandomListNode head){
    RandomListNode pNode = head;
    while(pNode!=null){
     RandomListNode pCloned = pNode.next;
     if(pNode.random!=null){
      pCloned.random = pNode.random.next; 
     }
     pNode = pCloned.next;
    }
   }
   //第三步，将第二步得到的链表拆分成两个链表
   public static RandomListNode splitNodes(RandomListNode head){
    RandomListNode pNode = head;
    RandomListNode clonedHead = null;
    RandomListNode clonedNode = null;
    if(pNode!=null){
     clonedHead = pNode.next;
     clonedNode = pNode.next;
     pNode.next = clonedNode.next;
     pNode = pNode.next;
    }
    while(pNode!=null){
     clonedNode.next = pNode.next;
     clonedNode = clonedNode.next;
     pNode.next = clonedNode.next;
     pNode = pNode.next;
    }
    return clonedHead;
   }
}

Zusammenfassung

Das obige ist der detaillierte Inhalt vonJava implementiert die gemeinsame Nutzung von Kopiercode für komplexe verknüpfte Listen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!