import java.util.HashMap; public class copylistwithRandom { //复制链表 public static class Node { public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } } //方法一:哈希表 public static Node copyListWithRand1(Node head) { HashMapmap = 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); } //方法二:节约空间的 *** 作 public static Node copyListWithRand2(Node head) { if (head == null) return null; Node cur = head; Node next = null; // copy node and link to every node while (cur != null) { // 节点复制 next = cur.next; cur.next = new Node(cur.value); cur.next.next = next; cur = next; } cur = head; Node curCopy = null; // set copy node rand while (cur != null) { next = cur.next.next; curCopy = cur.next; curCopy.rand = cur.rand != null ? cur.rand : 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; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)