public static Node<Integer> copy(Node<Integer> head){ 请接着写出一个方法复制链表
时间: 2023-12-10 19:02:25 浏览: 22
这里提供两种方法来复制链表:
方法一:使用 HashMap 存储原链表节点和复制节点的对应关系。
```java
public static Node<Integer> copy(Node<Integer> head) {
if (head == null) {
return null;
}
Map<Node<Integer>, Node<Integer>> map = new HashMap<>();
Node<Integer> cur = head;
// 第一遍遍历,将原链表节点和复制节点的对应关系存入 map 中
while (cur != null) {
map.put(cur, new Node<Integer>(cur.value));
cur = cur.next;
}
cur = head;
// 第二遍遍历,设置复制节点的 next 和 random 指针
while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
// 返回复制链表的头节点
return map.get(head);
}
```
方法二:在原链表的每个节点后面插入一个复制节点,然后设置复制节点的 random 指针和 next 指针,最后将复制节点和原节点分开。
```java
public static Node<Integer> copy(Node<Integer> head) {
if (head == null) {
return null;
}
Node<Integer> cur = head;
// 在每个节点后面插入一个复制节点
while (cur != null) {
Node<Integer> copy = new Node<Integer>(cur.value);
copy.next = cur.next;
cur.next = copy;
cur = copy.next;
}
cur = head;
// 设置复制节点的 random 指针
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
cur = head;
Node<Integer> copyHead = head.next;
// 将复制节点和原节点分开
while (cur != null) {
Node<Integer> copy = cur.next;
cur.next = copy.next;
if (copy.next != null) {
copy.next = copy.next.next;
}
cur = cur.next;
}
// 返回复制链表的头节点
return copyHead;
}
```