链表问题——复制含有随机指针节点的链表

小鱼儿 2022-06-03 03:55 131阅读 0赞

【题目】  
　　一种特殊的链表节点类描述如下：

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节点类型组成的无环单链表的头节点，请实现一个函数完成这个链表中所有结果的复制，并返回复制的新链表的头节点。

【代码】  
　　这里介绍两种解法，普通解法和进阶解法

class test
    {
        //普通解法
        public Node copyListWithRand1(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 Node copyListWithRand2(Node head)
        {
            if(head == null)
            {
                return null;
            }
            Node cur = head;
            Node next = null;
            while(cur != null)
            {
                next = cur.next;
                cur.next = new Node(cur.value);
                cur.next.next = next;
                cur = next;
            }
            cur = head;
            Node curCopy = null;
            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;
            while(cur != head)
            {
                next = cur.next.next;
                curCopy = cur.next;
                cur.next = next;
                curCopy.next = next != null ? next.next : null;
                cur = next;
            }
            return res;
        }
    }