拷贝有随机指针的链表

/*
思路：
1.将新节点放在老节点后。形成一种对应关系，此时不关注random节点；
2.根据位置的对应关系，设置新节点的random的值；
3.将新老链表进行分离【其实只需要分离出新链表就行了，我就是这样做的】
4.返回新链表的头节点。
*/
import java.util.*;
/**
 * 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 null;
        }
        RandomListNode cur = head;
        RandomListNode next = null;
        while(cur != null) {
            next = cur.next;
            cur.next = new RandomListNode(cur.label);
            cur.next.next = next;
            cur = next;
        }
        //设置新节点的rand指针
        cur = head;
        RandomListNode curNext = null;
        while(cur != null) {
            next = cur.next.next;
            curNext = cur.next;
            curNext.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }
        RandomListNode ret = head.next;
        cur = head;
        while(cur != null) {
            next = cur.next.next;
            curNext = cur.next;
            curNext.next = next == null ? null : next.next;
            cur = next;
        }
        return ret;
    }
}

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        /**
         *    首先复制原链表，复制的节点在原链表节点之后，得到 1->1`->2->2`->3->3`...
         *    然后复制随机指针，新链表的随机指针是原链表的下一个节点（例如 1->3 复制为 1`->3`）
         *    将链表拆分为两个链表， 一共遍历三遍，时间复杂度O(n)
         */
        if(head==null){
            return null;
        }
        // 复制链表
        RandomListNode p = head;
        while(p!=null){
            RandomListNode node = new RandomListNode(p.label);
            node.next = p.next;
            p.next = node;
            p = node.next;
        }
        // 复制随机指针
        p = head;
        RandomListNode q = head.next;
        while(p!=null){
            if(p.random!=null){
                q.random = p.random.next;
            }
            p = q.next;
            if(p!=null) q = p.next;
        }
        // 拆分两个链表
        p = head;
        q = head.next;
        RandomListNode nHead = head.next;
        while(p!=null){
            p.next = q.next;
            p = q.next;
            if(p!=null) {
                q.next = p.next;
                q = p.next;
            };
        }
        return nHead;
    }
}

public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode headMy = new RandomListNode(0);
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode cur = head;
        RandomListNode curMy = headMy;
        while (cur != null) {
            map.put(cur, new RandomListNode(cur.label));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            RandomListNode tmp = map.get(cur);
            curMy.next = tmp;

            curMy.next.random = map.get(cur.random);
            curMy.next.next = map.get(cur.next);
            
            curMy = curMy.next;
            cur = cur.next;
        }
        return headMy.next;
    }

public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null){
            return null;
        }
        RandomListNode cur = head;
        RandomListNode next = null;
        while (cur != null){
            next = cur.next;
            RandomListNode cp = new RandomListNode(cur.label);
            cur.next = cp;
            cp.next = next;
            cur = next;
        }
        cur = head;
        RandomListNode fast = head.next;
        while (fast != null){
            fast.random =  cur.random == null ? null :cur.random.next;
            if (fast.next == null){
                break;
            }
            fast = fast.next.next;
            cur = cur.next.next;
        }
        cur = head;
        fast = head.next;
        while (fast != null){
            if (fast.next == null){
                break;
            }
            next = fast.next.next;
            fast.next = next;
            fast = next;
        }
        return cur.next;
    }

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null)
            return null;
        //复制旧的指针，random指向null
        RandomListNode pNode = head;
        RandomListNode cHead = null, cNode = null;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        while (pNode != null) {
            RandomListNode node = new RandomListNode(pNode.label);
            node.next = null;
            node.random = null;

            if (pNode == head) {
                cHead = cNode = node;
            } else {
                cNode.next = node;
                cNode = cNode.next;
            }
            map.put(pNode, cNode);
            pNode = pNode.next;
        }
        //复制random指针
        for (Map.Entry<RandomListNode, RandomListNode> m : map.entrySet()) {
            m.getValue().random = map.get(m.getKey().random);
        }
        return cHead;
    }
}

// 第一步：将复制链表根据：原节点--->复制节点的模式进行创建（A->A'->B->B'），并把所有的随机指针random赋值为null
// 第二步：根据原节点的random指针指向（原节点A指向原节点B），更新复制节点的random（复制节点A’的random指向复制节点B‘）
// 第三步：将原链表和复制节点分离，返回复制链表


public class Solution {
    public RandomListNode copyRandomList(RandomListNode pHead) {
        if(pHead==null)
            return null;
        RandomListNode pCur = pHead;
        //复制next 如原来是A->B->C 变成A->A'->B->B'->C->C'
        while(pCur!=null){
            RandomListNode node = new RandomListNode(pCur.label);
            node.next = pCur.next;
            pCur.next = node;
            pCur = node.next;
        }
        pCur = pHead;
        //复制random pCur是原来链表的结点 pCur.next是复制pCur的结点
        while(pCur!=null){
            if(pCur.random!=null)
                pCur.next.random = pCur.random.next;
            pCur = pCur.next.next;
        }
        //head是复制的链表的头结点(第一个复制链表节点)
        RandomListNode head = pHead.next;
        //cur的作用就是代替head做操作
        RandomListNode cur = head;
        //Pcur作用是代替pHead做操作
        pCur = pHead;
        //拆分链表
        while(pCur!=null){
            //原链表指针更新
            pCur.next = pCur.next.next;
            if(cur.next!=null){
                //复制指针更新
                cur.next = cur.next.next;
            }
            //更新各自节点
            cur = cur.next;
            pCur = pCur.next;
        }
        return head;     
    }
}

//纯递归
import java.util.ArrayList;
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if(head==null) return null;
        RandomListNode h = new RandomListNode(head.label);
        f(head,h);
        return h;
    }
    public ArrayList<RandomListNode[]> f(RandomListNode p ,RandomListNode q ){
        if(p==null) return null;
        if(p.next==null) 
            q.next=null;
        else
        	q.next=new RandomListNode(p.next.label);
        q.random = p.random;
        ArrayList<RandomListNode[]> arr = f(p.next,q.next);
        if(arr!=null){
            if(p.random==null) return arr;
            boolean flag = true;
            for(int i=0;i<arr.size();i++){
                if(arr.get(i)[0]==p){
                    arr.get(i)[1].random=q;
                    arr.remove(i);
                    flag=false;
                    break;
                }
            }
            if(flag)
            	arr.add(new RandomListNode[]{p.random,q});
            if(arr.size()==0) return null;
            else return arr;
        }
        if(p.random==null) return null;
       	 ArrayList<RandomListNode[]> list = new ArrayList<RandomListNode[]>();
        list.add(new RandomListNode[]{p.random,q});
        return list;
    }
    
}

/**
 * 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) {
        //0.检查非法输入
        if(head == null){
            return null;
        }
        //创建新链表头结点
        RandomListNode newHead = new RandomListNode(0);
        /*1.第一次遍历，将所有结点复制一遍，而且每个结点连接到原来节点的后面*/
        RandomListNode current = head;
        while(current != null){
            //建立新结点
            RandomListNode tempNode = new RandomListNode(current.label);
            //将新结点指向原有结点的下一结点
            tempNode.next = current.next;
            //将当前结点连接到新结点
            current.next = tempNode;
            //指针前移动到原有链表的下一结点
            current = tempNode.next;
        }
        
        /*2.第二次遍历，调整新建结点的random指针*/
        current = head;
        while(current != null && current.next !=null){
            //由于random的特殊性，可能为空，因此需要提前判断
            if(current.random != null){
                //将复制结点的random指random结点的复制结点
                current.next.random = current.random.next;
            }
            current = current.next.next;
        }
        
        /*3.分离原有结点和复制结点*/
        newHead.next = head.next;
        current = head;
        RandomListNode help = head.next;
        // current->help->temp->
        while(help != null && help.next != null){
            //temp指向help结点的下一结点
            RandomListNode temp = help.next;
            //current->temp
            current.next = temp;
            //help->temp.next
            help.next = temp.next;
            //移动指针
            current = current.next;
            help = help.next;
        }
        return newHead.next;
    }
}

/**思路通过hashmap建立新旧节点间映射关系
 * Definition for singly-linked list with a random pointer.
 * class RandomListNode {
 *     int label;
 *     RandomListNode next, random;
 *     RandomListNode(int x) { this.label = x; }
 * };
 */
import java.util.*;
public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null)
            return null;
        
        HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
        RandomListNode cur = head;
        RandomListNode pre = null;
        RandomListNode preNew = null;
        RandomListNode newHead = new RandomListNode(head.label);
        map.put(head, newHead);
        preNew = newHead;
        while(cur.next != null) {
            pre = cur;
            cur = cur.next;
            RandomListNode newTempNode = new RandomListNode(cur.label);
            preNew.next = newTempNode;
            map.put(cur, newTempNode);
            preNew = newTempNode;
        }
        cur = head;
        pre = newHead;
        while(cur != null) {
            pre.random = map.get(cur.random);
            cur = cur.next;
            pre = pre.next;
        }
        return newHead;
    }
}

/**
 * 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 node=head;
        //step1:复制节点
        while(node!=null){
            //复制前一个节点
            RandomListNode copyNode=new RandomListNode(node.label);
            copyNode.next=node.next;
            copyNode.random=node.random;
            //把前一个节点的next指针指向新创建的节点
            node.next=copyNode;
            //node指向下一个要拷贝的节点
            node=node.next.next;
        }

        node=head.next;
        //step2：更新random指针
        while(node!=null){
            if(node.random!=null){
                node.random=node.random.next;
            }
            if(node.next!=null){
                node=node.next.next;
            }else{
                node=null;
            }
        }

        //step3:提取深度拷贝链表
        //创建深度拷贝链表的头结点
        RandomListNode deepListHead=head.next;
        //创建一个指针p，方便引用
        RandomListNode p=deepListHead;
        if(p.next==null){
            return deepList;
        }
        node=deepList.next.next;
        while(node!=null){
            p.next=node;
            if(node.next==null)
                node=node.next;
            else{
                node=node.next.next;
            }
            //更新p指针
             p=p.next;
        }
        return deepList;
    }
}

public class Solution {
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode f,randomhead,p;
        f=head;
        if(head==null)
            return head;
        while(f!=null){
            RandomListNode node=new RandomListNode(f.label);
            node.next=f.next;
            f.next=node;
            f=f.next.next;  
        }
        f=head;
        while(f!=null){
            if(f.random!=null)
            f.next.random=f.random.next;
            f=f.next.next;
        }
        f=head;
        p=randomhead=f.next;
        while(f!=null){
            f.next=f.next.next;
            if(f.next!=null)
            p.next=f.next.next;
            f=f.next;
            p=p.next;
        }
     return randomhead;   
    }
}

public RandomListNode copyRandomList(RandomListNode head) {
	RandomListNode iter = head, next; // First round: make copy of each node, // and link them together side-by-side in a single list. while (iter != null) { next = iter.next;

		RandomListNode copy = new RandomListNode(iter.label);
		iter.next = copy; copy.next = next;

		iter = next;
	} // Second round: assign random pointers for the copy nodes. iter = head; while (iter != null) { if (iter.random != null) {
			iter.next.random = iter.random.next;
		}
		iter = iter.next.next;
	} // Third round: restore the original list, and extract the copy list. iter = head;
	RandomListNode pseudoHead = new RandomListNode(0);
	RandomListNode copy, copyIter = pseudoHead; while (iter != null) { next = iter.next.next; // extract the copy copy = iter.next;
		copyIter.next = copy;
		copyIter = copy; // restore the original list iter.next = next;

		iter = next;
	} return pseudoHead.next;
}