leetcode.Q1744.复制带随机指针的链表

解析思路

leetcode 中等,题目描述点击这里

比较简单,链表结构可以通过遍历复制,关键是random节点如何处理,这里提供一个处理思路:

通过两次遍历来实现:

  • 第一次遍历建立新的链表,不处理random,遍历的同时将旧链表节点和新链表节点做一个一一对应
  • 第二次遍历处理random节点,根据map找到新链表的位置

代码

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
public class Q138 {
private static class Node {
int val;
Node next;
Node random;

public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}

public Node copyRandomList(Node head) {
//老节点和新节点的对应关系
Map<Node, Node> oldNewMap = new HashMap<>();
//建立虚拟头节点便于处理
Node res = new Node(0), tempNew = res, tempOld = head;
while (tempOld != null) {
tempNew.next = new Node(tempOld.val);
tempNew = tempNew.next;
//旧节点和新节点一一对应
oldNewMap.put(tempOld, tempNew);
tempOld = tempOld.next;
}
//再次便利将random关系处理好
while (head != null) {
if (head.random != null) {
oldNewMap.get(head).random = oldNewMap.get(head.random);
}
head = head.next;
}
return res.next;
}
}
本文原创发布于:https://blog.fleyx.com,转载请注明出处

如果本篇文章对您有帮助欢迎打赏哦!
微信打赏 支付宝打赏
关注公众号(烦嚣的人)
微信公众号