25. 复杂链表的复制

25. 复杂链表的复制

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


思路
注意本题的要点在于,输出结果中不要返回参数中的节点引用,所以不能直接将参数节点返回结果,而是要通过遍历的方式建立拥有新的节点的新链表。
解题思路:
1、遍历链表,复制每个结点,如复制结点A得到A1,将结点A1插到结点A后面;
2、重新遍历链表,复制老结点的随机指针给新结点,如A1.random = A.random.next;
3、拆分链表,将链表拆分为原链表和复制后的链表
思路图如下所示:



代码也分3步来解决这个问题。分别是:(要注意节点的next为空的情况)
第1次遍历,复制节点
第2次遍历,复制random指针
第3次遍历,拆分链表


代码实现

# -*- coding:utf-8 -*-
# class RandomListNode:
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None
class Solution:
    # 返回 RandomListNode
    def Clone(self, pHead):
        # write code here
        if not pHead:
            return pHead
        # 第1次遍历,复制节点
        head = pHead # 把参数复制到head中,免得后续操作影响pHead
        while(head):
            newNode = RandomListNode(head.label)
            newNode.next = head.next
            head.next = newNode
            head = newNode.next
        # 第2次遍历,复制random指针
        head = pHead
        while(head):
            newNode = head.next
            if head.random:
                newNode.random = head.random.next
            head = newNode.next
        # 第3次遍历,拆分链表
        head = pHead
        newHead = head.next # newHead是新链表的表头指针,先固定下来
        while(head):
            newNode = head.next
            head.next = newNode.next
            head = newNode.next
            if(head == None):
                newNode.next = None
            else:
                newNode.next = head.next
        return newHead
全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务