剑指offer(牛客)---复杂链表的复制

题目描述

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

    /*
    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 currentNode = pHead;
            //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
            while(currentNode != null){
                RandomListNode cloneNode = new RandomListNode(currentNode.label);
                RandomListNode nextNode = currentNode.next;
                currentNode.next = cloneNode;
                cloneNode.next = nextNode;
                currentNode = nextNode;
            }
             
            currentNode = pHead;
            //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
            while(currentNode != null) {
                currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
                currentNode = currentNode.next.next;
            }
             
            //3、拆分链表，将链表拆分为原链表和复制后的链表
            currentNode = pHead;
            RandomListNode pCloneHead = pHead.next;
            while(currentNode != null) {
                RandomListNode cloneNode = currentNode.next;
                currentNode.next = cloneNode.next;
                cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
                currentNode = currentNode.next;
            }
             
            return pCloneHead;
        }
    }

解题思路:在原链表的基础上在每个节点后面复制一个相同节点,然后在把链表拆分;

假设有下面这样一条链表:

第一步将phead节点复制给currentNode(为什么不在直接使用phead呢?因为,我们第二轮遍历的时候又得从头节点开始,所以我们得保留);

判断currentNode不等于null,开始复制;创建一个复制节点cloneNode并且给它一个当前结点的值,并将currenNode的下一个节点指向它,而原先currentNode的下一个节点现在就是下下一个节点了;就这样一直复制;

结束循环之后:

现在进入到第二个循环将老节点的随机结点赋给新结点( currentNode = pHead就表现出它的作用了,从头节点有开始遍历):

进入判断,不为空的之后,将当前节点的随机结点的下一个结点赋值给它(cloneNode.next==null?null:cloneNode.next.next),这里要理解,相当于A'的随机节点是C'(这道题最大的难度就在这里),然后循环赋值完毕:

现在开始拆分链表 ,拆分表我感觉太简单了,就没必要细讲了,可以看懂的.

总结:这道题主要还是要考虑随机指向这个问题,所以采用了这种链表分身赋值的方式解决.简单容易理解.

Java 面试宝典是大明哥全力打造的 Java 精品面试题，它是一份靠谱、强大、详细、经典的 Java 后端面试宝典。它不仅仅只是一道道面试题，而是一套完整的 Java 知识体系，一套你 Java 知识点的扫盲贴。

它的内容包括：

大厂真题：Java 面试宝典里面的题目都是最近几年的高频的大厂面试真题。
原创内容：Java 面试宝典内容全部都是大明哥原创，内容全面且通俗易懂，回答部分可以直接作为面试回答内容。
持续更新：一次购买，永久有效。大明哥会持续更新 3+ 年，累计更新 1000+，宝典会不断迭代更新，保证最新、最全面。
覆盖全面：本宝典累计更新 1000+，从 Java 入门到 Java 架构的高频面试题，实现 360° 全覆盖。
不止面试：内容包含面试题解析、内容详解、知识扩展，它不仅仅只是一份面试题，更是一套完整的 Java 知识体系。
宝典详情：https://www.yuque.com/chenssy/sike-java/xvlo920axlp7sf4k
宝典总览：https://www.yuque.com/chenssy/sike-java/yogsehzntzgp4ly1
宝典进展：https://www.yuque.com/chenssy/sike-java/en9ned7loo47z5aw

目前 Java 面试宝典累计更新 400+ 道，总字数 42w+。大明哥还在持续更新中，下图是大明哥在 2024-12 月份的更新情况：

想了解详情的小伙伴，扫描下面二维码加大明哥微信【daming091】咨询

同时，大明哥也整理一套目前市面最常见的热点面试题。微信搜[大明哥聊 Java]或扫描下方二维码关注大明哥的原创公众号[大明哥聊 Java] ，回复【面试题】即可免费领取。

阅读全文