Java implémente le partage de code de copie de listes chaînées complexes

Cet article présente principalement la question d'entretien Java - partager le code de copie pour implémenter une liste chaînée complexe. L'éditeur pense que c'est assez bon et qu'il a une valeur de référence. Les amis qui en ont besoin peuvent en apprendre davantage.

Questions finales de programmation en ligne d'Alibaba, écrivez-les et partagez-les avec tout le monde

Il existe une liste chaînée à sens unique, chaque nœud contient un pointeur aléatoire, pointant vers un nœud dans cette liste chaînée ou dans Vide, écrivez une fonction de copie complète pour copier l'intégralité de la liste chaînée, y compris le pointeur aléatoire. Dans la mesure du possible, envisagez des exceptions possibles.

L'algorithme est le suivant :

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

Résumé

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!