阿里終面在線編程題，寫出來與大家分享一下
有一個單向鏈表，每個節點都包含一個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面試題-實現復雜鏈表的復制代碼分享的全部內容，感興趣的朋友可以繼續參閱：Java輸出鏈表倒數第k個節點、Java語言實現反轉鏈表代碼示例、Java編程實現從尾到頭打印鏈表代碼實例以及本站其他相關專題，希望對大家有所幫助。如有不足之處，歡迎留言指出，小編一定及時更正，給大家提供更好的閱讀體驗及幫助，感謝朋友們對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
