Java教程

【算法】复制有随机指针的单链表

本文主要是介绍【算法】复制有随机指针的单链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

左程云算法与数据结构课 https://www.bilibili.com/video/BV13g41157hK?p=2&spm_id_from=pageDriver

题目

一种特殊的单链表节点描述如下

class Node {
    int value;
    Node next;
    Node rand;
    Node(int val) {
        value = val;
    }
}

rand 指针是单链表节点结构中新增的指针,rand 可能指向链表中的任意一个位置,也可能指向 null。给定一个由 Node 节点类型组成的无环单链表的头节点 head,请实现一个函数完成链表的复制,并返回复制的新链表的头节点。要求时间复杂度O(N),空间复杂度O(1)。

题解

设原链表如下

image-20220119012144351

生成克隆节点并放在原节点的下一个位置。

image-20220119012155511

一对一对地把节点拿出来把 rand 指针复制。例如把 1 和 1’ 节点拿出来,1 的 rand 指向 3,故 1‘ 的 rand 指向 3 的下一个节点,即 3’ 节点。

image-20220119012531700

最后分裂成新老链表即可。

image-20220119013305954

image-20220119013312555

public class CopyListWithRandom {
    static class Node {
        int value;
        Node next;
        Node rand;
        Node(int val) {
            value = val;
        }
    }
    public static Node copyListWithRand(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Node next = null;
        //复制新节点放在老节点后面
        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        //设置复制节点的 rand 指针
        cur = head;
        Node curCopy = null;
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            curCopy.rand = cur.rand != null ? cur.rand.next : null;
            cur = next;
        }
        //分裂成新老链表
        Node res = head.next;
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next : null;
            cur = next;
        }
        return res;
    }
}
这篇关于【算法】复制有随机指针的单链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!