金九银十之复制含有随机指针节点的链表_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;
}

} ```