算法练习(9)-复杂带随机指针的单链表
2021/10/23 17:09:46
本文主要是介绍算法练习(9)-复杂带随机指针的单链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
所谓带随机指针的链表,结构如下:
class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } }
除next外,还有一个随机指针random,随机指向链表中的某个元素(当然 :random也可能为null). 复制的难度在于, 新节点刚new出来时,其random指向的另外1个“新”节点,可能还没复制出来(即:首次无法确定新节点的random该指向谁,除非所有老节点全复制完)
有二种做法: 1、借助额外的Map记录“新-老”节点的映射public Node copyRandomList(Node head) { if (head==null){ return null; } Node h = head; Map<Node,Node> map = new HashMap<>(); Node newHead = new Node(head.val); Node curr = newHead; //第一轮,复制节点,random挂空,同时记录处理过的老节点与新节点的映射关系 while(head!=null){ if (head.next!=null){ Node newNext = new Node(head.next.val); curr.next = newNext; } map.put(head,curr); head = head.next; curr = curr.next; } head = h; //第二轮,处理random指向,通过map映射,查到random指向的新节点 while(head!=null){ Node newNode = map.get(head); if (head.random!=null){ newNode.random = map.get(head.random); } head = head.next; } return newHead; }
2、如果要求空间复杂度为O(1),还有1个比较巧妙的思路
a、 先把每个节点复制一份, 挂在自己身后,相当于A -> B -> C 变成 A -> A' -> B -> B' -> C -> C' b、 每2轮,处理random时,通过身后的“影子”,就能找到random的新节点在哪 c、 将链表分离, A -> A' -> B -> B' -> C -> C' 变成 A -> B -> C 和A' -> B' -> C' 返回A'public Node copyRandomList(Node head) { if (head==null){ return head; } Node curr = head; //复制自身,挂在身后 while(curr!=null){ Node newNode = new Node(curr.val); newNode.next = curr.next; curr.next = newNode; curr = curr.next.next; } //复制random curr = head; while(curr!=null){ if (curr.random!=null){ curr.next.random = curr.random.next; } curr = curr.next.next; } //分离链表 curr = head; Node newHead = head.next; while(curr!=null){ Node newCurr = curr.next; curr.next = curr.next.next; if (newCurr.next!=null){ newCurr.next = newCurr.next.next; } curr = curr.next; } return newHead; }
这篇关于算法练习(9)-复杂带随机指针的单链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01Java部署教程:新手入门指南
- 2024-11-01Java部署教程:从入门到实践
- 2024-11-01Java订单系统教程:新手入门指南
- 2024-11-01Java分布式教程:新手入门指南
- 2024-11-01Java管理系统教程:新手入门详解
- 2024-11-01Java监控系统教程:从入门到实践
- 2024-11-01SpringCloud Alibaba入门:轻松搭建微服务架构
- 2024-11-01Swagger入门:新手必读指南
- 2024-11-01Swagger入门:轻松搭建API文档
- 2024-11-01uni-APP入门:新手快速上手指南