在Java中,复制一个链表可以通过多种方式实现，具体取决于链表的结构和类型，以下是几种常见的复制链表的方法：
使用循环遍历复制
这种方法适用于单向链表,可以通过循环遍历链表，同时创建新的节点，将原链表的节点数据复制到新链表的节点中。
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public ListNode copyList(ListNode head) {
if (head == null) {
return null;
}
ListNode current = head;
ListNode dummy = new ListNode(0); // 创建一个哑节点作为新链表的头节点
ListNode tail = dummy; // 尾节点初始化为哑节点
while (current != null) {
ListNode newNode = new ListNode(current.val); // 创建新节点
tail.next = newNode; // 将新节点链接到新链表
tail = newNode; // 更新尾节点
current = current.next; // 移动到原链表的下一个节点
}
return dummy.next; // 返回新链表的头节点
}
使用递归复制
递归方法适用于任何类型的链表,包括单向链表、双向链表和循环链表，递归方法的基本思想是，如果原链表不为空，则创建一个新节点，并将原链表的当前节点值复制到新节点中，然后递归地复制原链表的下一个节点。
public ListNode copyListRecursive(ListNode head) {
if (head == null) {
return null;
}
ListNode newNode = new ListNode(head.val); // 创建新节点
newNode.next = copyListRecursive(head.next); // 递归复制下一个节点
return newNode;
}
使用HashMap复制
这种方法适用于任何类型的链表,包括单向链表、双向链表和循环链表，通过使用HashMap来存储原链表节点到新链表节点的映射关系，可以有效地复制整个链表。
public ListNode copyListWithHashMap(ListNode head) {
if (head == null) {
return null;
}
Map<ListNode, ListNode> map = new HashMap<>();
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
ListNode current = head;
while (current != null) {
map.put(current, new ListNode(current.val)); // 将原节点和新节点映射
tail.next = map.get(current); // 将新节点链接到新链表
tail = map.get(current); // 更新尾节点
current = current.next; // 移动到原链表的下一个节点
}
return dummy.next; // 返回新链表的头节点
}
FAQs
Q1：如何处理循环链表复制？
A1： 处理循环链表复制时，需要先找到循环的起点，然后使用HashMap来存储原链表节点到新链表节点的映射关系，一旦确定了循环的起点，就可以遍历整个链表，确保每个节点都被正确复制。
Q2：如何处理双向链表复制？
A2： 复制双向链表时，除了复制节点的值外，还需要复制节点的next和prev指针，可以使用HashMap来存储原链表节点到新链表节点的映射关系，并在复制过程中更新next和prev指针。
原创文章，发布者：酷盾叔，转转请注明出处：https://www.kd.cn/ask/199896.html
