首页 > 代码库 > [leetcode]Copy List with Random Pointer

[leetcode]Copy List with Random Pointer

2024-07-16 02:27:57   224人阅读

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.

剑指offer中的原题

算法思路：

遍历原list的每一个节点，对每一个节点生成一个copy节点，插到原节点的后面。完成next的拷贝

第二遍扫描，对每一个原节点的random节点，其copy节点的random应该为原节点random.next。完成random的拷贝

第三遍扫描，将copy list取下来。

【注意】：分解原list和copy list时候，要完整的把原list给组装起来。不能破坏原list的结构。

 1 public class Solution { 2     public RandomListNode copyRandomList(RandomListNode head) { 3             if(head == null) return null; 4             RandomListNode node = head; 5             while(node != null){ 6                 RandomListNode tem = new RandomListNode(node.label); 7                 tem.next = node.next; 8                 node.next = tem; 9                 node = node.next.next;10             }11             node = head;12             while(node != null){13                 RandomListNode next = node.next;14                 if(node.random != null)15                     next.random = node.random.next;16                 node = node.next.next;17             }18             RandomListNode hhead = new RandomListNode(0);19             RandomListNode pointer = hhead;20             node = head;21             while(node != null){22                 pointer.next = node.next;23                 pointer = node.next;24                 node.next = node.next.next;25                 node = node.next;26             }27             return hhead.next;28         }29 }

 


联系
我们