java算法題解LeetCode35復(fù)雜鏈表的復(fù)制實(shí)例
題目
AC 劍指 Offer 35. 復(fù)雜鏈表的復(fù)制請(qǐng)實(shí)現(xiàn) copyRandomList 函數(shù)，復(fù)制一個(gè)復(fù)雜鏈表。在復(fù)雜鏈表中，每個(gè)節(jié)點(diǎn)除了有一個(gè) next 指針指向下一個(gè)節(jié)點(diǎn)，還有一個(gè) random 指針指向鏈表中的任意節(jié)點(diǎn)或者 null。
示例 1：
輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
輸入：head = [[1,1],[2,1]] 輸出：[[1,1],[2,1]]
示例 3：
輸入：head = [[3,null],[3,0],[3,null]] 輸出：[[3,null],[3,0],[3,null]]
示例 4：
輸入：head = [] 輸出：[] 解釋：給定的鏈表為空（空指針），因此返回 null。
提示： -10000 <= Node.val <= 10000 Node.random 為空（null）或指向鏈表中的節(jié)點(diǎn)。 節(jié)點(diǎn)數(shù)目不超過(guò) 1000 。
解題思路
哈希的做法，在大多數(shù)公司的面試官面前并不是一個(gè)滿意的答案，所以需要知道原地修改的解法才能夠從容面對(duì)面試。 原地修改解法流程： 假設(shè)三個(gè)節(jié)點(diǎn)初始如下
1.第一次遍歷，復(fù)制一個(gè)新的節(jié)點(diǎn)在原有節(jié)點(diǎn)之后，如 1 -> 2 -> 3 -> null 復(fù)制完就是 1 -> 1 -> 2 -> 2 -> 3 - > 3 -> null 第一次遍歷，構(gòu)建的節(jié)點(diǎn)，random還未連接起來(lái)，如下圖
我們需要把A指向C，因?yàn)槌跏嫉腁的random指針指向了C，那是不是有這樣的公式： A->random = A->random->next
2.第二次遍歷，從頭開(kāi)始遍歷鏈表，通過(guò) cur.next.random = cur.random.next 可以將復(fù)制節(jié)點(diǎn)的隨機(jī)指針串起來(lái)，當(dāng)然需要判斷 cur.random 是否存在
3.第三次遍歷，就比較簡(jiǎn)單了，只是找出這些相鄰節(jié)點(diǎn)，組成結(jié)果就可以
class Solution {
public Node copyRandomList(Node head) {
// if head == null,則return null
if (head == null) {
return null;
}
// 第一次遍歷， 1 -> `1` -> 2 -> `2` -> 3 - > `3` -> null
Node cur = head;
while (cur != null) {
Node node = new Node(cur.val);
Node temp = cur.next;
cur.next = node;
cur.next.next = temp;
cur = cur.next.next;
}
// 第二次遍歷，填充random節(jié)點(diǎn)
cur = head;
while (cur != null) {
Node newNode = cur.next;
newNode.random = cur.random != null ? cur.random.next : null;
cur = cur.next.next;
}
// 第三次遍歷，拆分
Node headNew = head.next;
for (Node node = head; node != null; node = node.next) {
Node nodeNew = node.next;
node.next = node.next.next;
nodeNew.next = (nodeNew.next != null) ? nodeNew.next.next : null;
}
return headNew;
}
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
}以上就是java算法題解LeetCode35復(fù)雜鏈表的復(fù)制實(shí)例的詳細(xì)內(nèi)容，更多關(guān)于java算法復(fù)雜鏈表復(fù)制的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
Spring?Boot整合Bootstrap的超詳細(xì)步驟
之前做前端開(kāi)發(fā),在使用bootstrap的時(shí)候都是去官網(wǎng)下載,然后放到項(xiàng)目中,在頁(yè)面引用,下面這篇文章主要給大家介紹了關(guān)于Spring?Boot整合Bootstrap的超詳細(xì)步驟,需要的朋友可以參考下2023-05-05
這篇文章主要介紹了Java七大過(guò)程模型詳解,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了Java將微信和支付寶支付的個(gè)二維碼合二為一的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-08-08
intellij idea查看方法被哪些類引用過(guò)(推薦)
這篇文章主要介紹了intellij idea查看方法被哪些類引用過(guò),本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-08-08
在Java中,System.out.printf方法用于格式化輸出,格式化字符串`%.6f`表示浮點(diǎn)數(shù)保留6位小數(shù),其他格式化選項(xiàng)包括`%d`（整數(shù)）、`%s`（字符串）和`%e`（科學(xué)計(jì)數(shù)法）,示例代碼展示了如何使用這些格式化選項(xiàng),感興趣的朋友一起看看吧2025-02-02
java傳入時(shí)間戳返回LocalDateTime的實(shí)現(xiàn)方法
這篇文章主要介紹了java傳入時(shí)間戳返回LocalDateTime的實(shí)現(xiàn)方法,在Java中將時(shí)間戳轉(zhuǎn)換為L(zhǎng)ocalDateTime時(shí)需要注意時(shí)區(qū)問(wèn)題,因?yàn)長(zhǎng)ocalDateTime不包含時(shí)區(qū)信息,文中通過(guò)代碼介紹的非常詳細(xì),需要的朋友可以參考下2024-11-11
java存儲(chǔ)以及java對(duì)象創(chuàng)建的流程(詳解)
下面小編就為大家?guī)?lái)一篇java存儲(chǔ)以及java對(duì)象創(chuàng)建的流程(詳解)。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-05-05
這篇文章主要介紹了Java反射和動(dòng)態(tài)代理的概念、使用方法和應(yīng)用場(chǎng)景,反射允許在運(yùn)行時(shí)動(dòng)態(tài)地獲取類的信息和調(diào)用類的方法,而動(dòng)態(tài)代理則可以在不修改原有代碼的情況下,為方法調(diào)用添加額外的功能2025-02-02
使用sharding-jdbc實(shí)現(xiàn)水平分表的示例代碼
本文主要介紹了sharding-jdbc實(shí)現(xiàn)水平分表，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-11-11
Java Servlet中Response對(duì)象的使用方法
本文介紹了Java Servlet中Response對(duì)象的使用方法，包括設(shè)置響應(yīng)頭、設(shè)置響應(yīng)編碼、向客戶端發(fā)送數(shù)據(jù)、重定向等操作，同時(shí)介紹了常用的響應(yīng)狀態(tài)碼和響應(yīng)類型，幫助讀者更好地理解和掌握Servlet中Response對(duì)象的用法2023-05-05