請實現(xiàn) copyRandomList 函數(shù)，復(fù)制一個復(fù)雜鏈表。在復(fù)雜鏈表中，每個節(jié)點除了有一個 next 指針指向下一個節(jié)點，還有一個 random 指針指向鏈表中的任意節(jié)點或者 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é)點。
節(jié)點數(shù)目不超過 1000 。

思路：

每個結(jié)點后面復(fù)制一個和他相同的結(jié)點連在后面

代碼：

/*

//?Definition?for?a?Node.

class?Node?{

????int?val;

????Node?next;

????Node?random;

?

????public?Node(int?val)?{

????????this.val?=?val;

????????this.next?=?null;

????????this.random?=?null;

????}

}

*/

class?Solution?{

????public?Node?copyRandomList(Node?head)?{

????????if(head==null)

????????{

????????????return?head;

????????}

????????Node?p?=?head;

????????while(p!=null)

????????{

????????????Node?node?=?new?Node(p.val);

????????????node.next?=?p.next;

????????????p.next?=?node;

????????????p?=?p.next.next;

????????}

????????p?=?head;

????????while(p!=null&&p.next!=null)

????????{

????????????if(p.random!=null)

????????????{

?????????????????p.next.random?=?p.random.next;

????????????}

????????????p?=?p.next.next;

????????}

????????Node?x?=?head.next;

????????Node?q?=?head;

????????while(q.next!=null)

????????{

????????????Node?t?=?q.next;

????????????q.next?=?q.next.next;

????????????q?=?t;

????????}

????????return?x;

????}

}

總結(jié)

以上是生活随笔為你收集整理的【剑指offer】面试题35：复杂链表的复制（Java）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。