随笔记录

算法-链表-复制带随机指针的链表

2022-4-5 diaba 算法

package com.jiucaiyuan.net.algrithm.linked;

import java.util.HashMap;

/**
 * 【问题】复制带有随机指针节点的链表
 * 【要求】时间复杂度O(N)，空间复杂度O(1)
 * 【思路】如果不是空间复杂度O(1)的限制，可以使用Map，暂存新老节点之间的关系，
 * 然后再补齐rand字段，但是有O(1)限制，所以在克隆出新节点时，放到该节点之后，
 * 变成注入这个结构：1——>1`——>2——>2`——>3——>3`——>4——>4`——>5——>5`
 * 然后再遍历next、next.next，补齐rand，然后再拆出来新老链表，返回新链表的头结点
 *
 * @Author jiucaiyuan  2022/4/5 21:46
 * @mail services@jiucaiyuan.net
 */

public class CopyListWithRand {
    /** 使用额外空间
     * @param head
     * @return
     */
    public static Node copyListWithRand1(Node head, int value) {
        if (head == null){
            return null;
        }
        //把所有原节点放到map的key中，并克隆节点作为map的value
        HashMap<Node,Node> map = new HashMap<>();
        Node curr = head;
        while (curr != null){
            map.put(curr, new Node(curr.value));
            curr = curr.next;
        }

        //循环设置新节点的next和rand
        curr = head;
        while (curr != null){
            //curr 老的
            //map.get(curr) 新的
            map.get(curr).next = map.get(curr.next);
            map.get(curr).rand = map.get(curr.rand);
            curr = curr.next;
        }
        return map.get(head);
    }

    /** 不使用额外空间
     * @param head
     * @return
     */
    public static Node copyListWithRand2(Node head, int value) {
        if (head == null){
            return null;
        }
        //copy node : 1——>2——>3——>null  to  1——>1`——>2——>2`——>3——>3`——>null
        Node curr = head;
        Node next = null;
        while (curr != null){
            next = curr.next;
            curr.next = new Node(curr.value);
            curr.next.next = next;
        }

        curr = head;
        Node currCopy = null;
        //set copy node rand
        //1——>1`——>2——>2`——>3——>3`——>null
        while (curr != null){
            next = curr.next.next;
            currCopy = curr.next;
            currCopy.rand = next.rand != null ? next.rand.next:null;
            curr = next;
        }

        Node res = head.next;
        curr = head;
        //split 1——>1`——>2——>2`——>3——>3`——>null to 1——>2——>3——>null and 1`——>2`——>3`——>null
        while (curr != null){
            next = curr.next.next;
            currCopy = curr.next;
            curr.next = next;
            currCopy.next = next != null ? next.next:null;
            curr = next;
        }
        return res;
    }

    static class Node{
        int value;
        Node next;
        Node rand;
        public Node(int value){
            this.value = value;
        }
    }
}