剑指offer之025-复杂链表的复制

题目描述

输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)

思路

方案1:

  • 第一步:遍历老链表,构建正常的链表,用一个map记录p到new_p
  • 第二步:新老链表同步next移动,对比记录random指针。

p 1->2->3->4 map | | | | new_p 1->2->3->4

需要借助O(n)的空间,时间复杂度为o(n)

方案2:

不需要借助O(n)的空间,时间复杂度为o(n)

老新链表交叉存储,奇数位置为老链表,偶数位置新链表复制前一个位置。

新链表random即为旧链表random的后一个位置。

p1->p1′->p2->p2′->…->pn->pn’

class RandomListNode:
    def __init__(self, x):
        self.label = x
        self.next = None
        self.random = None


# 返回 RandomListNode
def Clone(pHead):
    # write code here
    if not pHead: return None
    p = pHead
    new_h = RandomListNode(p.label)
    pre_p = new_h
    random_map = {pHead: new_h}
    p = p.next
    while p:
        new_p = RandomListNode(p.label)
        random_map[p] = new_p
        pre_p.next = new_p
        pre_p = pre_p.next
        p = p.next
    p = pHead
    new_p = new_h
    while p:
        random_p = p.random
        if random_p:
            new_p.random = random_map[random_p]

        p = p.next
        new_p = new_p.next

    return new_h

p = RandomListNode(1)
p.next = RandomListNode(2)
p.next.next = RandomListNode(3)
p.next.next.next = RandomListNode(4)
p.next.next.next.next = RandomListNode(5)
print(Clone(p))

关于明柳梦少

坚守自己的原则,不随波逐流。