Home > Java > Javagetting Started > body text

How to copy a multi-way linked list in java

王林
Release: 2020-10-30 16:12:21
forward
2328 people have browsed it

How to copy a multi-way linked list in java

Multi-directional linked list structure such as

(Video tutorial recommendation: java course)

public class Node{
    public int value;
    public Node next;
    public Node rand;
    public Node(int data){
        this.value = data;
       }
}
Copy after login

Method 1: Use HashMap structure

public class CopyFromMultiNode {
    public static void main(String[] args){
        int[] array = {12,3,4,5,6,77,6,54,56,6,7,87,15,15,15};
        //数组转Node
        Node head = array2node(array);
        Node help = head;
        System.out.print("处理前     ");
        while(help != null){
            System.out.print(help.value + " ");
            help = help.next;
        }
 
        //使用HashMap结构
        Node res = copyFromRand1(head);
        System.out.println();
        System.out.print("处理后结果:");
        while(res != null){
            System.out.print(res.value+" ");
            res = res.next;
        }
    }
 
    //使用HashMap结构
    public static Node copyFromRand1(Node head){
        Node cur = head;
        HashMap<Node, Node> map = new HashMap<>();
        while(cur != null){
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }
        return map.get(head);
    }
 
    //数组转Node功能,供测试使用
    public static Node array2node(int[] array){
        Node head = new Node(array[0]);
        Node cur = head;
        for(int i=1; i<array.length; i++){
            cur.next = new Node(array[i]);
            cur = cur.next;
        }
        return head;
    }
 
    //基础node节点结构
    public static class Node{
        public int value;
        public Node next;
        public Node rand;
        public Node(int data){
            this.value = data;
        }
    }
}
Copy after login

2. Use several valid variable methods without other structures

    //使用几个有效变量方法
    //替换方法一的copyFromRand1方法
    public static Node copyFromRand2(Node head){
        Node next = null;
        Node cur = head;
        //1 -> 2 -> 3 -> 4 ==> 1 -> 1` -> 2 -> 2` -> 3 -> 3` -> 4 -> 4
        //完成链表拼接
        while(cur != null){
            next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        Node curCopy = null;
        //添加Node的rand值
        while(cur != null){
            next = cur.next.next;
             curCopy = cur.next.next;
             curCopy = cur.rand != null? cur.rand.next: null;
            cur = next;
        }
        Node res = head.next;
        cur = head;
        //拆分
        //  1 -> 1` -> 2 -> 2` -> 3 -> 3` -> 4 -> 4
        //   ==>  1 -> 2 -> 3 -> 4  和 1`-> 2`-> 3`-> 4`
        while(cur != null){
            next = cur.next.next;
            curCopy = cur.next;
            cur.next = next;
            curCopy.next = next != null ? next.next:null;
            cur = next;
        }
        return res;
    }
Copy after login

Recommended related tutorials: Getting started with java

The above is the detailed content of How to copy a multi-way linked list in java. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:csdn.net
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template