【剑指Offer】025——复杂链表的复制（链表）

题目描述

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

解题思路

file

参考代码

Java

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;
    RandomListNode(int label) {
        this.label = label;
    }
}
public class Solution {
    public RandomListNodeClone(RandomListNode pHead)
    {
        if (pHead == null) return null;
        // 复制节点 A->B->C 变成 A->A'->B->B'->C->C'
        RandomListNode head = pHead;  // 不改变phead
        while (head != null) {
            RandomListNode node = new RandomListNode(head.label); // 新的结点 A'
            node.next = head.next;  // 连接到原始链表的下一个结点A'->B
            head.next = node;       // 原始链表的下一个结点更新到新的结点A->A'
            head = node.next;       // 往前走一步（原始链表的下一个）head = B
        }
        // 复制random
        head = pHead;
        while(head != null){
            // 新node的随机值
            head.next.random = head.random == null ? null : head.random.next;
            head = head.next.next; // 跳两下到原始的下一个值
        }
        // 拆分
        head = pHead;
        RandomListNode chead = head.next; // 开始复制，需要返回的值
        while(head != null){
            RandomListNode node = head.next; //  A'
            head.next = node.next;           // 下一个B
            // A'->B'
            node.next = node.next == null ? null : node.next.next;
            head = head.next;                // 更新head到
        }
        return chead;
    }
}

Python

# -*- 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 None
        # 复制
        head = pHead
        while head is not None:
            node = RandomListNode(head.label)
            node.next = head.next
            head.next = node
            head = node.next
        # 复制random
        head = pHead
        while head is not None:
            # 两个随机对应相邻关系
            head.next.random = None if not head.random else head.random.next
            head = head.next.next
        # 拆分
        head = pHead
        chead = head.next
        while head is not None:
            node = head.next      # 获取x'
            head.next = node.next # 获取next
            node.next = None if not node.next else node.next.next 
            head = head.next
        return chead

个人订阅号

image