金九銀十之複製含有隨機指針節點的鏈表
- 小知識,大挑戰!本文正在參與“程序員必備小知識”創作活動。
文字題解
1、第一種方式是通過用hashmap的方式來實現複製一個帶有隨機指針的鏈表 ,通過對各個節點進行存儲完成
2、第二種方式是通過對老鏈表進行復制來完成,將鏈表的下一個節點 指向一個複製出來的相同的節點,將原來的下一個節點放在複製出來的節點的後面
代碼實現
```
/*
* 利用hashMap的方式來複制一個帶有隨機指針的鏈表
*
* @param head 鏈表的頭結點
* @return 新鏈表的頭結點
/
private static Node copyLinkListWithRand1(Node head) {
final HashMap
/* * 通過對老鏈表進行復制來完成 * @param head 鏈表的頭結點 * @return 新鏈表的頭結點 / private static Node copyLinkListWithRand2(Node head) { if (head == null) { return null; } Node cur = head; Node next = null;
//copy node and link to every one
//將鏈表的下一個節點指向一個複製出來的相同的節點,將原來的下一個節點放在複製出來的節點後面
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.value);
cur.next.next = next;
cur = next;
}
cur = head;
Node copyNode = null;
// set copy node rand
while (cur != null) {
next = cur.next.next;
copyNode = cur.next;
copyNode.rand = cur.rand != null ? cur.rand.next : null;
cur = next;
}
Node res = head.next;
cur = head;
//split 將複製的鏈表從鏈表中分割出來,將原鏈表恢復原樣
while (cur != null) {
next = cur.next.next;
copyNode = cur.next;
cur.next = next;
copyNode.next = next != null ? next.next : null;
cur = next;
}
return res;
}
private static class Node { public int value; public Node next; public Node rand;
public Node(int data) {
this.value = data;
}
} ```