您好,登錄后才能下訂單哦!
阿里終面在線編程題,寫出來與大家分享一下
有一個(gè)單向鏈表,每個(gè)節(jié)點(diǎn)都包含一個(gè)random指針,指向本鏈表中的某個(gè)節(jié)點(diǎn)或者為空,寫一個(gè)深度拷貝函數(shù),拷貝整個(gè)鏈表,包括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); } //第一步,復(fù)制鏈表任意結(jié)點(diǎn)N并創(chuàng)建新結(jié)點(diǎ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; } } //第二步,設(shè)置復(fù)制出來的結(jié)點(diǎn) 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; } } //第三步,將第二步得到的鏈表拆分成兩個(gè)鏈表 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; } }
總結(jié)
以上就是本文關(guān)于Java面試題-實(shí)現(xiàn)復(fù)雜鏈表的復(fù)制代碼分享的全部?jī)?nèi)容,感興趣的朋友可以繼續(xù)參閱:Java輸出鏈表倒數(shù)第k個(gè)節(jié)點(diǎn)、Java語言實(shí)現(xiàn)反轉(zhuǎn)鏈表代碼示例、Java編程實(shí)現(xiàn)從尾到頭打印鏈表代碼實(shí)例以及本站其他相關(guān)專題,希望對(duì)大家有所幫助。如有不足之處,歡迎留言指出,小編一定及時(shí)更正,給大家提供更好的閱讀體驗(yàn)及幫助,感謝朋友們對(duì)本站的支持!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。