如何实现链表的拷贝
时间: 2023-07-12 15:08:08 浏览: 38
链表的拷贝可以通过遍历原链表,逐个创建新节点,并复制原节点的值到新节点中来实现。具体步骤如下:
1. 遍历原链表,逐个创建新节点,并将原节点的值复制到新节点中。
2. 在创建新节点的同时,将新节点插入到新链表的末尾。
3. 如果原链表中的节点有指向其他节点的指针(比如 next 指针),则需要在新链表中对应节点的 next 指针指向新链表中对应的节点。
4. 最终返回新链表的头节点即可。
下面是一个示例代码:
```python
class Node:
def __init__(self, val):
self.val = val
self.next = None
def copyLinkedList(head: Node) -> Node:
if not head:
return None
# 创建新链表的头节点
newHead = Node(head.val)
newTail = newHead
# 遍历原链表
p = head.next
while p:
# 创建新节点
newNode = Node(p.val)
# 将新节点插入到新链表的末尾
newTail.next = newNode
newTail = newNode
# 如果原节点有指向其他节点的指针,则需要更新新节点的指针
if p.next:
newNode.next = Node(p.next.val)
# 继续遍历原链表
p = p.next
return newHead
```
需要注意的是,上述代码只是简单示例,实际应用中可能需要考虑更多的特殊情况。比如原链表中可能存在环,这时需要特别处理。