這篇文章主要介紹了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中文網其他相關文章!