Gold nine silver ten copy a linked list with random pointer nodes

• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Text antithesis

1. The first way is to copy a linked list with random Pointers in the form of HashMap, which is accomplished by storing each node

2. The second method is to copy the old linked list. The next node of the linked list points to the same copied node, and the original next node is placed after the copied node

Code implementation

/** * use hashMap to copy a list with a random pointer ** @param head * @return new list head */ private static Node copyLinkListWithRand1(Node head) { final HashMap<Node, Node> 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); } private static Node copyLinkListWithRand2(Node head) {private static Node copyLinkListWithRand2(Node head) { if (head == null) { return null; } Node cur = head; Node next = null; //copy node and link to every one //copy the next node to a copy of the same node, put the original next node after the copy of the node 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 split the copied list from the linked list and restore the original list as is 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; }}Copy the code