题目
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
思路 + 代码
参考 https://github.com/CyC2018/CS-Notes/blob/master/notes/%E5%89%91%E6%8C%87%20Offer%20%E9%A2%98%E8%A7%A3%20-%2030~39.md#35-%E5%A4%8D%E6%9D%82%E9%93%BE%E8%A1%A8%E7%9A%84%E5%A4%8D%E5%88%B6
分为三步:
1. 在每个节点的后面插入复制的节点。
2. 每个复制的节点 random 赋值。
3. 拆分。
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
|
public class Solution { public RandomListNode Clone(RandomListNode pHead) { if(pHead == null) return null; RandomListNode cur = pHead; while(cur!=null){ RandomListNode tmp = new RandomListNode(cur.label); tmp.next = cur.next; cur.next = tmp; cur = tmp.next; } cur = pHead; while(cur!=null){ if(cur.random!=null) cur.next.random = cur.random.next; cur = cur.next.next; } cur = pHead; RandomListNode res = cur.next; while(cur.next!=null){ RandomListNode tmp = cur.next; cur.next = tmp.next; cur = tmp; } return res; } }
|