首頁  >  文章  >  Java  >  Java實作複雜鍊錶的複製程式碼分享

Java實作複雜鍊錶的複製程式碼分享

黄舟
黄舟原創
2017-10-17 10:06:151410瀏覽

這篇文章主要介紹了Java面試題-實現複雜鍊錶的複製程式碼分享,小編覺得還挺不錯的,具有參考價值,需要的朋友可以了解下。

阿里終面線上程式設計題,寫出來與大家分享一下

        有單向鍊錶,每個節點都包含一個random指針,指向本鍊錶中的某個節點或為空,寫一個深度拷貝函數,拷貝整個鍊錶,包括random指標。盡可能考慮可能的異常情況。

演算法如下:


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

#總結

以上是Java實作複雜鍊錶的複製程式碼分享的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn