Java面試題-實現(xiàn)復雜鏈表的復制代碼分享

更新時間：2017年10月16日 10:53:54 作者：diu_brother

這篇文章主要介紹了Java面試題-實現(xiàn)復雜鏈表的復制代碼分享，小編覺得還是挺不錯的，具有參考價值，需要的朋友可以了解下。

阿里終面在線編程題，寫出來與大家分享一下

有一個單向鏈表，每個節(jié)點都包含一個random指針，指向本鏈表中的某個節(jié)點或者為空，寫一個深度拷貝函數(shù)，拷貝整個鏈表，包括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并創(chuàng)建新結點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面試題-實現(xiàn)復雜鏈表的復制代碼分享的全部內容，感興趣的朋友可以繼續(xù)參閱：Java輸出鏈表倒數(shù)第k個節(jié)點、Java語言實現(xiàn)反轉鏈表代碼示例、Java編程實現(xiàn)從尾到頭打印鏈表代碼實例以及本站其他相關專題，希望對大家有所幫助。如有不足之處，歡迎留言指出，小編一定及時更正，給大家提供更好的閱讀體驗及幫助，感謝朋友們對本站的支持！

您可能感興趣的文章: