复制含有随机指针节点的链表
【题目】 一种特殊的链表节点类描述如下:
public class Node {
public int value;
public Node next;
public Node rand;
public Node(int data)
{ this.value = data; }}
Node类中的value是节点值,next指针和正常单链表中next指针的意义一 样,都指向下一个节点,rand指针是Node类中新增的指针,这个指针可 能指向链表中的任意一个节点,也可能指向null。 给定一个由Node节点类型组成的无环单链表的头节点head,请实现一个 函数完成这个链表中所有结构的复制,并返回复制的新链表的头节点。
进阶:不使用额外的数据结构,只用有限几个变量,且在时间复杂度为 O(N)内完成原问题要实现的函数。
/*
* 采用hashmap,第一次遍历,将结构存入hashmap,完成第一次拷贝,第二次遍历,
* 通过map.get(node).next = map.get(node.next)完成next节点和rand节点的连接,如:
* map.get(1).next = map.get(1.next)
* 1'.next = map.get(2)
* 最后返回头结点,完成链表拷贝;
*/
public class 复制含有随机节点的单链表 { public static class Node{ public int value; public Node next; public Node rand; public Node(int data) { this.value = data; } } public static Node copy1(Node head) { 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); } public static void main(String[] args) { Node head = null; Node res1 = null; Node res2 = null; printRandLinkedList(head); res1 = copy1(head); printRandLinkedList(res1); res2 = copy2(head); printRandLinkedList(res2); printRandLinkedList(head); System.out.println("========================="); head = new Node(1); head.next = new Node(2); head.next.next = new Node(3); head.next.next.next = new Node(4); head.next.next.next.next = new Node(5); head.next.next.next.next.next = new Node(6); head.rand = head.next.next.next.next.next; // 1 -> 6 head.next.rand = head.next.next.next.next.next; // 2 -> 6 head.next.next.rand = head.next.next.next.next; // 3 -> 5 head.next.next.next.rand = head.next.next; // 4 -> 3 head.next.next.next.next.rand = null; // 5 -> null head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4 printRandLinkedList(head); res1 = copy1(head); printRandLinkedList(res1); res2 = copy2(head); printRandLinkedList(res2); printRandLinkedList(head); System.out.println("========================="); } /* * 不需要额外辅助空间的方法: * 第一次遍历,完成链表每一个节点的拷贝及连接 * 1——>2——>3——>null * 1——>1'——>2——>2'——>3——>3'——>null * 第二次遍历,完成链表rand节点的拷贝和连接 * 每次拿出节点1和1',然后找出1的rand节点,1的rand节点的下一个节点就是1'对应的rand节点 * 第三次遍历,完成节点分离,rand节点不相交,完成新老next节点的分离即可 */ private static Node copy2(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.next : null; cur = next; } Node res = head.next; cur = head; // split while (cur != null) { next = cur.next.next; curCopy = cur.next; cur.next = next; curCopy.next = next != null ? next.next : null; cur = next; } return res; } private static void printRandLinkedList(Node head) { Node cur = head; System.out.print("order: "); while (cur != null) { System.out.print(cur.value + " "); cur = cur.next; } System.out.println(); cur = head; System.out.print("rand: "); while (cur != null) { System.out.print(cur.rand == null ? "- " : cur.rand.value + " "); cur = cur.next; } System.out.println(); } }