復(fù)制含有隨機(jī)指針節(jié)點(diǎn)的鏈表

一種特殊的鏈表節(jié)點(diǎn)類描述如下：

public class Node {public int value;public Node next;public Node rand;public Node(int data) {this.value = data;} }
Node 類中的 value 是節(jié)點(diǎn)值，next 指針和正常單鏈表中 next 指針的意義一樣，都指向下一個(gè)節(jié)點(diǎn)，rand 指針是 Node
類中新增的指針，這個(gè)指針可能指向鏈表中的任意一個(gè)節(jié)點(diǎn)，也可能指向 null。
給定一個(gè)由 Node 節(jié)點(diǎn)類型組成的無環(huán)單鏈表的頭節(jié)點(diǎn) head，請實(shí)現(xiàn)一個(gè)函數(shù)完成這個(gè)鏈表中所有結(jié)構(gòu)的復(fù)制，并返
回復(fù)制的新鏈表的頭節(jié)點(diǎn)。例如：鏈表 1->2->3->null，假設(shè) 1 的 rand 指針指向 3，2 的 rand 指針指向 null，3
的 rand 指針指向 1。復(fù)制后的鏈表應(yīng)該也是這種結(jié)構(gòu)，比如，1->2->3->null，1 的 rand 指針指向 3，2 的 rand
指針指向 null，3 的 rand 指針指向 1，最后返回 1。
時(shí)間復(fù)雜度為 O(N)，額外空間復(fù)雜度 O(1)


思路：兩種實(shí)現(xiàn)辦法，一種是使用額外空間，建立一個(gè)哈希表，用于存儲原鏈表節(jié)點(diǎn)與對應(yīng)的新建鏈表節(jié)點(diǎn)的對應(yīng)，方法是首先遍歷一遍原鏈表，可以將新建鏈表每個(gè)節(jié)點(diǎn)的next指針按照原鏈表的連接順序連接，即哈希表中的對應(yīng)關(guān)系是：1->1',2->2',3->3'，1'.next->2'.next->3'.next->null,再遍歷第二次原鏈表，根據(jù)原鏈表的rand指針和哈希表中原鏈表與新鏈表每個(gè)節(jié)點(diǎn)的對應(yīng)關(guān)系，將新鏈表中每個(gè)節(jié)點(diǎn)的rand指針按照原鏈表中每個(gè)節(jié)點(diǎn)的rand指向順序連接，即可實(shí)現(xiàn)，即1'.rand->3'.rand,2'.rand->null,3'.rand->1'。第二種辦法，將原鏈表的每個(gè)節(jié)點(diǎn)新建并用原鏈表中每個(gè)節(jié)點(diǎn)的next指針連接，即1->1'->2->2'->3->3'->null,之后遍歷原鏈表的每個(gè)節(jié)點(diǎn)的rand指針，即可利用原鏈表的每個(gè)節(jié)點(diǎn)的next指向新鏈表的拷貝節(jié)點(diǎn)，對新鏈表的每個(gè)節(jié)點(diǎn)的rand指針進(jìn)行賦值，即可實(shí)現(xiàn)。

public static class Node{public int value;public Node next;public Node rand;public Node(int data){this.value = data;} }public static Node copyListWithRand_1(Node head){HashMap<Node, Node> map = new HashMap<Node,Node>();Node cur = head;while(cur != null){map.put(cur, new Node(cur.value));cur = cur.next;}cur = head;while(cur != null){map.get(cur).next = map.get(cur.next);map.get(cur).rand = map.get(cur.rand);cur = cur.next;}return map.get(head); } public static Node copyListWithRand_2(Node head){if(head == null){return null;}Node cur = head;Node next = null;while(cur != null){next = cur.next;cur.next = new Node(cur.value);cur.next.next = next;cur = next;}cur = head;Node curCopy = null;while(cur != null){next = cur.next.next;curCopy = cur.next;curCopy.rand = cur.rand != null ? cur.rand.next : null;cur = next;}Node res = head.next;cur = head;while(cur != null){next = cur.next.next;curCopy = cur.next;cur.next = next;curCopy.next = next != null ? next.next : null;cur = next;}return res; }

總結(jié)

以上是生活随笔為你收集整理的如何复制一个含有随机指针节点的链表的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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