面试题35. 复杂链表的复制
程序员文章站
2022-05-06 11:03:53
...
题目:
题解:
1. 题解一:HashMap
- 第一遍遍历,复制节点的 val ,next 和 random 暂时为空,并将源节点和克隆节点形成映射存放在一个 HashMap 中。
- 第二遍遍历,将拷贝的新的节点组织成一个链表。
2. 题解二:原地修改
1. 解释一:
哈希的做法,在大多数公司的面试官面前并不是一个满意的答案,所以需要知道原地修改的解法才能够从容面对面试。
原地修改解法流程:
- 复制一个新的节点,放在原有节点之后(将拷贝节点放到原节点后面),如 1 -> 2 -> 3 -> null 复制完就是 1 -> 1’ -> 2 -> 2’ -> 3 - > 3’ -> null;
- 从头开始遍历链表,通过 cur.next.random = cur.random.next 可以将拷贝节点的随机指针串起来,当然需要判断 cur.random 是否存在;
- 将复制完的链表一分为二,分离拷贝节点和原节点,变成1->2->3和1’->2’->3’两个链表,后者就是答案。
注意:
node.next 是 node 复制出来的节点 ,node.random.next 也是 node.random 复制出来的节点。
2. 解释二:
- 输入如下图 [[1,2],[2,3],[3,null],[4,null]]
- 复制源节点。
- 生成克隆节点的 random 指针。
- 将原链表和克隆链表分离。
实现的时候,谨记:源节点的 next 就是它的克隆节点。
代码:
1. 代码一:HashMap
// 方法1:
public static Node copyRandomList(Node head) {
if(head == null)
{
return null;
}
// map中存的是(原节点,拷贝节点)的一个映射
Map<Node, Node> map = new HashMap<>();
Node p = head;
while(p != null)
{
Node clone = new Node(p.val);
map.put(p, clone);
p = p.next;
}
p = head;
// 将拷贝的新的节点组织成一个链表
while(p != null)
{
map.get(p).next = map.get(p.next);
map.get(p).random = map.get(p.random);
p = p.next;
}
return map.get(head);
}
2. 代码二:原地修改
// 方法2:
public static Node copyRandomList(Node head) {
if(head == null)
{
return null;
}
// 完成链表节点的复制
Node cur = head;
while(cur != null)
{
Node clone = new Node(cur.val);
clone.next = cur.next;
cur.next = clone;
cur = cur.next.next;
}
// 完成链表复制节点的随机指针复制
cur = head;
while(cur != null)
{
if(cur.random != null) // 注意判断原来的节点有没有random指针
{
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
// 将链表一分为二
cur = head;
Node curCopy = head.next;
Node headCopy = head.next;
while(cur != null)
{
cur.next = cur.next.next;
cur = cur.next;
if(curCopy.next != null)
{
curCopy.next = curCopy.next.next;
curCopy = curCopy.next;
}
}
return headCopy;
}
参考:
上一篇: 面试题35. 复杂链表的复制
下一篇: HTML+CSS+JS 实现登录注册界面