复制链表

复制链表主要有三种解决方法：使用哈希表、拆分链表、使用递归。

1. 使用哈希表：

class Node:
    def __init__(self, val=None, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyLinkedList(head):
    if not head:
        return None

    node_dict = {}
    curr = head
    # 第一次遍历，复制节点值，并建立原节点与新节点的映射关系
    while curr:
        node_dict[curr] = Node(curr.val)
        curr = curr.next

    curr = head
    # 第二次遍历，设置新节点的next和random指针
    while curr:
        node_dict[curr].next = node_dict.get(curr.next)
        node_dict[curr].random = node_dict.get(curr.random)
        curr = curr.next

    return node_dict[head]

2. 拆分链表：

class Node:
    def __init__(self, val=None, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyLinkedList(head):
    if not head:
        return None

    curr = head
    # 第一次遍历，将新节点插入到原节点后面
    while curr:
        new_node = Node(curr.val)
        new_node.next = curr.next
        curr.next = new_node
        curr = new_node.next

    curr = head
    # 第二次遍历，设置新节点的random指针
    while curr:
        curr.next.random = curr.random.next if curr.random else None
        curr = curr.next.next

    # 第三次遍历，拆分新节点和原节点
    curr = head
    new_head = head.next
    while curr.next:
        tmp = curr.next
        curr.next = curr.next.next
        curr = tmp

    return new_head

3. 使用递归：

class Node:
    def __init__(self, val=None, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyLinkedList(head):
    if not head:
        return None

    if hasattr(head, 'visited'): # 已经复制过的节点直接返回
        return head.visited

    new_node = Node(head.val)
    head.visited = new_node

    new_node.next = copyLinkedList(head.next)
    new_node.random = copyLinkedList(head.random)

    return new_node