现在有一个这样的链表:链表的每一个节点都附加了一个随机指针,随机指针可能指向链表中的任意一个节点或者指向空。
请对这个链表进行深拷贝。
/* 思路: 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) { if(head ==null)return null; RandomListNode q = head; while(q!=null){//复制旧节点 RandomListNode newNode = new RandomListNode(q.label); newNode.next = q.next; q.next = newNode; q= newNode.next; } RandomListNode copy=head,p=head.next; while(copy!=null){//复制随机指针 if(copy.random!=null) p.random = copy.random.next; copy= p.next; if(copy!=null)p=copy.next; } RandomListNode re = head.next; p=head; q=head.next; while(p!=null){//断开新旧返回新链表 p.next = q.next; p=q.next; if(p!=null){ q.next=p.next; q=p.next; } } return re; } }
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; } }
import java.util.ArrayList; import java.util.HashMap; public class Solution { public RandomListNode copyRandomList(RandomListNode head) { if (head==null){ return null; } HashMap<RandomListNode,RandomListNode> nextMap=new HashMap<>(); HashMap<RandomListNode, ArrayList<RandomListNode>> randomMap=new HashMap<>(); RandomListNode copyHead=new RandomListNode(head.label); RandomListNode current=copyHead; nextMap.put(head,copyHead); while (head!=null){ if (head.next!=null){ RandomListNode next=new RandomListNode(head.next.label); current.next=next; nextMap.put(head.next,next); if (randomMap.containsKey(head.next)){ ArrayList<RandomListNode> arrayList=randomMap.get(head.next); for (RandomListNode node:arrayList){ node.random=next; } randomMap.remove(head.next); } } if (head.random!=null){ if (nextMap.containsKey(head.random)){ current.random=nextMap.get(head.random); }else if (randomMap.containsKey(head.random)){ ArrayList<RandomListNode> randomList=randomMap.get(head.random); randomList.add(current); randomMap.put(head.random,randomList); }else{ ArrayList<RandomListNode> randomList=new ArrayList<>(); randomList.add(current); randomMap.put(head.random,randomList); } } current=current.next; head=head.next; } return copyHead; } }
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;
}