首页 > 代码库 > LeetCode——Copy List with Random Pointer
LeetCode——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.
原题链接:https://oj.leetcode.com/problems/copy-list-with-random-pointer/
题目:给定一个链表,当中的每一个节点包括有一个额外的随机指针指向链表中的随意其它节点或空。
返回链表的一份深度复制。
思路:复制源链表中的每个节点到新链表中(仅仅考虑next)。复制随机指针关系到新链表中(仅仅考虑random.next),此时新链表的长度是源链表的2倍了。此时修正随机指针为正确的指向关系。
public RandomListNode copyRandomList(RandomListNode head) { if(head == null) return null; RandomListNode p = head; while(p != null){ RandomListNode copy = new RandomListNode(p.label); copy.next = p.next; p.next = copy; p = copy.next; } p = head; while(p != null){ if(p.random != null) p.next.random = p.random.next; p = p.next.next; } p = head; RandomListNode newHead = head.next; while(p != null){ RandomListNode tmp = p.next; p.next = tmp.next; if(tmp.next != null) tmp.next = tmp.next.next; p = p.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; } }
LeetCode——Copy List with Random Pointer
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。