算法初级——复制含有随机节点的链表

复制含有随机指针节点的链表
【题目】 一种特殊的链表节点类描述如下:
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)
* 最后返回头结点,完成链表拷贝;
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
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<Node,Node> map = new HashMap<Node,Node>();
        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();
       
    }

}
0 条评论
发表一条评论