138. Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.
题意：深拷贝一个有next和random的链表

如果采用暴力的方法，在确定新的链表里的random指针的指向时，需要遍历旧链表一遍，这样时间复杂度就为O(N^2)了。

思路

在旧的链表的后面插入每个元素的拷贝。这样，在确定random的时候，我们只需要new.random=old.random.next 就能确定了。

三步：

1.在旧链表上的每个节点后面插入一个拷贝的节点
2.在确定新的节点的random指针指向正确的节点
3.还原旧链表，拼接新链表

注意：这里没有专门的头节点，head即为链表的第一个元素

/**
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
public class Solution {
   public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null)
            return head;
       	RandomListNode p=head;
        while(p!=null)
        {
            RandomListNode copyNode=new RandomListNode(p.label);
            copyNode.next=p.next;
            copyNode.random=p.random;
            p.next=copyNode;
            p=p.next.next;
        }
        p=head;
        while(p!=null)
        {
            RandomListNode copyNode=p.next;
            if(p.random!=null)
            {
                copyNode.random=p.random.next;
            }
            p=p.next.next;
        }
        //RandomListNode newHead=new RandomListNode(0);
        RandomListNode newHead=head.next;
        //newHead.next=head.next.next;
        p=head;
        RandomListNode q=newHead;
        
        while(p.next.next!=null)
        {
            p.next=p.next.next;
            q.next=q.next.next;
            p=p.next;
            q=q.next;
        }
        p.next=null;
        return newHead;
    }
}

深拷贝与浅拷贝

因为题中涉及到了，就复习一下
对于C++中的拷贝构造函数，如果我们定义了一个student类

class Student
{
public:
	Student();
	{
		cout<<"student";
	}
private:
	string m_strName;
}

int main(void)
{
	Student stu1;
	Student stu2=stu1;
	Student stu3(stu1);
	return 0;
}

只打印了一次，说明只调用了一次构造函数。
stu2与stu3调用了拷贝构造函数

拷贝构造函数

如果没有自定义的拷贝构造函数，系统会自动生成一个默认的拷贝构造函数
当采用直接初始化或复制初始化实例对象时，系统会调用拷贝构造函数。

如何定义拷贝构造函数

格式：类名(const 类名& 变量名)
如

Student(const Student& stu)
{

}

class Student
{
public:
	Student()
	{
		m_strName="rui";
	}
	Student(const Student& stu)
	{
		m_strName = stu.m_strName;
	}
	void info()
	{
	cout << m_strName << endl;
	}
private:
	String m_strName;
}

int main()
{
	Student stu1;
	Student stu2 = stu1;
	Student stu3(stu1);
	stu1.info();
	stu2.info();
	stu3.info();
	system("pause");
}

Student(const Student& stu)
{
m_strName = stu.m_strName;
}

在进行拷贝时，值就由上面这个拷贝函数进行了浅拷贝，即值拷贝。

如果我们在类的数据成员中加入指针，则在进行浅拷贝的时候，两个对象的指针指向同一地址。如下面的例子

当我们释放掉arr1指向的内存，如果再销毁arr2，则也需要释放arr2指向的内存，同一块内存被释放了两次，计算机就会崩溃

运行了一次析构函数就报错了，因为运行arr2的析构函数时，会再次释放同一块地址。