复杂链表的复制（Java实现）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了复杂链表的复制（Java实现），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1239字，纯文字阅读大概需要2分钟。

内容图文

1.题目

2.解法

/*
public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}
*/

public class Solution {
    public RandomListNode Clone(RandomListNode pHead) {
        if(pHead == null) {
            return null;
        }
        RandomListNode curNode = pHead;
        RandomListNode nextNode = null;
        //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
        while (curNode != null) {
            RandomListNode cloneNode = new RandomListNode(curNode.label);
            nextNode = curNode.next;
            cloneNode.next = nextNode;
            curNode.next = cloneNode;
            curNode = nextNode;
        }
       
        
        curNode = pHead;
        //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
        while(curNode != null) {
            // 为什么是random.next，因为原结点后面紧跟复制的结点
            curNode.next.random = (curNode.random == null ? null : curNode.random.next);
            curNode = curNode.next.next;
        }

        //3、拆分链表，将链表拆分为原链表和复制后的链表
        curNode = pHead;
        RandomListNode cloneHead = pHead.next;
        RandomListNode cloneNode = null;
        while (curNode != null) {
            cloneNode = curNode.next;
            curNode.next = cloneNode.next;
            // 如果cloneNode.next为空的话
            cloneNode.next =  (cloneNode.next == null ? null : cloneNode.next.next);
            curNode = curNode.next;
        }
        return cloneHead;
    }
}

时间复杂度为O(3n),空间复杂度为O(n)

内容总结

以上是互联网集市为您收集整理的复杂链表的复制（Java实现）全部内容，希望文章能够帮你解决复杂链表的复制（Java实现）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端