开发者社区> woooow> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

复杂链表的复制

简介: 题目描述:有一个复杂链表,其结点除了有一个Next指针指向下一个结点外,还有一个random指向链表中的任意结点或者NULL。其链表的定义如下: public class RandomListNode { int label; Rand...
+关注继续查看

题目描述:有一个复杂链表,其结点除了有一个Next指针指向下一个结点外,还有一个random指向链表中的任意结点或者NULL。其链表的定义如下:

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

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

请实现 public RandomListNode Clone(RandomListNode pHead) 函数实现克隆一个链表。


解决思路:

  • 暴力的解法:首先只复制链表,不管random指针。然后再遍历原链表,复制random指针。复制random指针的方法是根据原链表从头开始,而指向复制链表的指针也同时开始,判断random指针是指向哪一个结点,然后根据位置对应,把复制链表的指针的位置赋值给random。好吧,其实画个图很简单。


    img_c80a1fbdfa5b9cbf96f0c760c5e09720.jpe
import java.util.*;

public class Main {

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

        public RandomListNode(int label){
            this.label = label;
        }
    }

    public RandomListNode Clone(RandomListNode pHead){
        if(pHead == null)
            return null;
        RandomListNode temp = pHead;
        RandomListNode head = new RandomListNode(temp.label);
        RandomListNode p = head;
        if(temp.next != null)
            temp = temp.next;
        //首先把只复制基本的链表

        while (temp != null){
            RandomListNode node = new RandomListNode(temp.label);
            p.next = node;
            node.next = null;
            p = p.next;
            temp = temp.next;
        }
        //然后复制random指针
        p = head;
        temp = pHead;
        while (p != null){
            if(temp.random == null){
                p.random = null;
                p = p.next;
                temp = temp.next;
                continue;
            }

            RandomListNode t = pHead;
            RandomListNode q = head;
            while(t != null){ //t和q只需要判断一个就行
                if(temp.random == t)
                    break;
                t = t.next;
                q = q.next;
            }

            p.random = q;
            p = p.next;
            temp = temp.next;
        }
        return head;
    }

    public static void main(String[] args) {
        RandomListNode node1 = new Main().new RandomListNode(1);
        RandomListNode node2 = new Main().new RandomListNode(2);
        RandomListNode node3 = new Main().new RandomListNode(3);
        RandomListNode node4 = new Main().new RandomListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;
        node1.random = null;
        node3.random = node1;
        RandomListNode head = new Main().Clone(node1);
        System.out.println(head);
        System.out.println(head.random);
        head = head.next;
        System.out.println(head.random);
        head = head.next;
        System.out.println(head.random);
    }
}

  • 本题一种巧妙的解法是,将每个复制后的结点都跟在原结点后面,步骤如下:
    1.复制每个结点,如复制结点A得到A1,并将A1插到结点A后面。
    2.重新遍历链表,复制老结点的随机指针给新结点,如A1.random = A.random.next
    3.拆分链表,将原链表拆分成原链表和复制后的链表
import java.util.*;

public class Main {

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

        public RandomListNode(int label){
            this.label = label;
        }
    }

    public RandomListNode Clone(RandomListNode pHead){
        if(pHead == null)
            return null;
        RandomListNode currentNode = pHead;
        //1.复制每个结点,如复制结点A得到A1,将A1插到A后面
        while (currentNode != null){
            RandomListNode copyNode = new RandomListNode(currentNode.label);
            RandomListNode p = currentNode.next;
            copyNode.next = p;
            currentNode.next = copyNode;
            currentNode = p;
        }

        //2.重新遍历链表,复制老结点的随机指针给新结点,如A1.random = A.random.next
        currentNode = pHead;
        while (currentNode != null){
            currentNode.next.random = (currentNode.random == null) ? null : currentNode.random.next;
            currentNode = currentNode.next.next;
        }

        //3.拆分链表,将原链表拆分成原链表和复制后的链表
        currentNode = pHead;
        RandomListNode copyHead = currentNode.next;
        while (currentNode != null){
            RandomListNode p = currentNode.next;
            currentNode.next = p.next;
            if(p.next != null)
                p.next = p.next.next;
            currentNode = currentNode.next;
        }
        return copyHead;
    }

    public static void main(String[] args) {
        RandomListNode node1 = new Main().new RandomListNode(1);
        RandomListNode node2 = new Main().new RandomListNode(2);
        RandomListNode node3 = new Main().new RandomListNode(3);
        RandomListNode node4 = new Main().new RandomListNode(4);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = null;
        node1.random = null;
        node3.random = node1;
        RandomListNode head = new Main().Clone(node1);
        System.out.println(head);
        System.out.println(head.random);
        head = head.next;
        System.out.println(head.random);
        head = head.next;
        System.out.println(head.random);
    }
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【LeetCode】第16天 - 234. 回文链表
【LeetCode】第16天 - 234. 回文链表
0 0
LeetCode笔记 | 链表(ing)
LeetCode笔记 | 链表(ing)
0 0
刷LeetCode链表之前你需要掌握的设置结点技巧C++
在c++的线性表中,如何用ListNode设置好结点呢?我们往往因为不熟悉指针和内存分配的原理,而在初学阶段不能正确的设置好结点,我总结了俩种不同情况设置结点的情况,这里引用LeetCode的几个题目为例
0 0
LeetCode排序链表C++解法(详解)
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表
0 0
leetcode 链表的中间结点
给定一个头结点为 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。
0 0
leetcode 删除链表的倒数第 N 个结点
给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。
0 0
LeetCode 23合并K个升序链表&24两两交换链表中的节点
给你一个链表数组,每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中,返回合并后的链表。
0 0
LeetCode 25K 个一组翻转链表&26删除排序数组中的重复项
给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
0 0
LeetCode 86分割链表&87扰乱字符串
给定一个链表和一个特定值 x,对链表进行分隔,使得所有小于 x 的节点都在大于或等于 x 的节点之前。
0 0
+关注
woooow
我不生产bug,我只是bug的搬运工
文章
问答
文章排行榜
最热
最新
相关电子书
更多
移动与复制
立即下载
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载