金九銀十之複製含有隨機指標節點的連結串列_BuildF

小知識，大挑戰！本文正在參與“程式設計師必備小知識”創作活動。

文字題解

1、第一種方式是通過用hashmap的方式來實現複製一個帶有隨機指標的連結串列，通過對各個節點進行儲存完成

2、第二種方式是通過對老連結串列進行復制來完成，將連結串列的下一個節點指向一個複製出來的相同的節點，將原來的下一個節點放在複製出來的節點的後面

程式碼實現

``` /* * 利用hashMap的方式來複制一個帶有隨機指標的連結串列 * * @param head 連結串列的頭結點 * @return 新連結串列的頭結點 / private static Node copyLinkListWithRand1(Node head) { final HashMap map = new HashMap<>(); 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); }

/* * 通過對老連結串列進行復制來完成 * @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;
}

} ```