LeetCode138. 复制带随机指针的链表

题目链接:LeetCode138

 第一步:复制结点,复制的结点放在待复制的结点后,依然组成一个单链表  第二步:串接随机指针  第三步:将原单链表与复制链表拆开

class Solution {

    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) {
            return null;
        }

        copyNode(head);
        linkRandomPointer(head);

        return splitList(head);
    }

    /**
     * 复制结点,复制的结点放在待复制的结点后,依然组成一个单链表
     *
     * @param head 链表头
     */
    public void copyNode(RandomListNode head) {
        // 记录当前要被复制的缜
        RandomListNode node = head;
        while (node != null) {
            // 复制一个新的结点
            RandomListNode copyNode = new RandomListNode(node.label);
            // 将结点串接到被复制的结点后,并且依然组成单链表
            copyNode.next = node.next;
            node.next = copyNode;
            node = copyNode.next;
        }
    }

    /**
     * 串接随机指针
     *
     * @param head 链表头
     */
    public void linkRandomPointer(RandomListNode head) {
        // 记录当前要被复制的缜
        RandomListNode node = head;
        while (node != null) {
            // 随机指针有指向某个具体的结点
            if (node.random != null) {
                // 串接node被复制结点的随机指针
                node.next.random = node.random.next;
            }

            // 指向下一个被复制的结点
            node = node.next.next;
        }
    }

    /**
     * 将链表拆分,还原原来的链表,并且组装拷贝的链表
     *
     * @param head 链表头
     * @return 拷贝的新链表头
     */
    public RandomListNode splitList(RandomListNode head) {
        // 新链表头
        RandomListNode copyHead = head.next;
        // 当前处理的被复制的结点
        RandomListNode node = head;
        // 当前复制的结点
        RandomListNode copy;

        while (node != null){
            // 指向复制结点
            copy = node.next;

            // node.next指向下一个被复制的结点
            node.next = copy.next;

            // 下一个被复制的结点不为null
            if (node.next != null) {
                // copy.next指向下一个复制的结点
                copy.next = node.next.next;
            }

            // node指向下一个要被处理的被复制结点
            node = node.next;
        }
        return copyHead;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏软件开发 -- 分享 互助 成长

java中大数类的学习

java中提供了大数类BigInteger和BigDecimal分别表示大整数类和大浮点数类,这两个类都在java.math.*包中,因此每次必须在开头处引用该...

27750
来自专栏小灰灰

JDK容器学习之Queue: PriorityQueue

优先级队列 PriorityQueue 单端队列,队列中的元素有优先级的顺序 ? 1. 底层数据结构 // 存储队列元素的数组 transient Object...

24450
来自专栏Java进阶之路

ArrayList 源码剖析

13500
来自专栏令仔很忙

集合详解(二)----ArrayList源代码剖析(JDK1.7)

ArrayList是List类的一个典型的实现,是基于数组实现的List类,因此,ArrayList封装了一个动态的、可变长度的Object[]数组。Arra...

7810
来自专栏撸码那些事

【图解数据结构】 线性表

27650
来自专栏coolblog.xyz技术专栏

ArrayList 源码详细分析

ArrayList 是一种变长的集合类,基于定长数组实现。ArrayList 允许空值和重复元素,当往 ArrayList 中添加的元素数量大于其底层数组容量时...

44780
来自专栏猿人谷

线性表简介

学习数据结构 -> 线性表 -> 线性表的介绍     线性表是一种典型的数据结构, 线性结构的基本特点是线性表中的数据元素是有序且有限的, 在线性结构中...

22280
来自专栏青玉伏案

算法与数据结构(十) 二叉排序树的查找、插入与删除(Swift版)

在上一篇博客中,我们主要介绍了四种查找的方法,包括顺序查找、折半查找、插入查找以及Fibonacci查找。上面这几种查找方式都是基于线性表的查找方式,今天博客中...

22270
来自专栏marsggbo

链表、头指针、头结点

 图1为线性表(ZHAO, QIAN, SUN, LI, ZHOU, WU, ZHENG, WANG)的逻辑状态。头指针 指示链表中第一个结点(即第一个数据元素...

26170
来自专栏格子的个人博客

Java源码阅读之ArrayList - JDK1.8

当你对某件事情很感兴趣的时候,时间的流逝在感知中都模糊了(是不是很文艺,绕口得都快听不懂了),通俗来说,就是时间过得很快。

21050

扫码关注云+社区

领取腾讯云代金券