剑指Offer——复杂链表的复制转载

1，标题说明，主题说明

输入复杂链表(每个节点有节点值，有两个指针，一个指向下一个节点，一个指向任意节点)，复制后返回结果为复杂链表head(注意，请不要在输出结果中返回节点引用。(注意，请不要在输出中返回节点引用，否则程序会直接返回空)

2，代码实现，代码实现

package com.baozi.offer;

import java.util.HashMap;

/**
 * 输入一个复杂的链表(每个节点中都有节点值，以及两个指针，一个指向下一个节点，一个指向任何节点)。
 * 结果是复制后的复杂链接表head。
 * (注意，请不要在输出中返回参数中的节点引用，否则判断程序将直接返回空)
 *
 * @author BaoZi
 * @create 2019-07-12-19:42
 */
public class Offer21 {
    public static void main(String[] args) {
        Offer21 offer21 = new Offer21();
        RandomListNode r1 = new RandomListNode(1);
        RandomListNode r2 = new RandomListNode(2);
        RandomListNode r3 = new RandomListNode(3);
        RandomListNode r4 = new RandomListNode(4);
        RandomListNode r5 = new RandomListNode(5);
        r1.next = r2;
        r2.next = r3;
        r3.next = r4;
        r4.next = r5;
        r5.next = null;
        r1.random = r3;
        r2.random = r4;
        r3.random = r2;
        r4.random = r2;
        r5.random = r1;
        RandomListNode clone = offer21.Clone(r1);
        RandomListNode temp = clone;
        while (temp != null) {
            System.out.println(temp.label+"--" + temp.random.label);
            temp = temp.next;
        }

    }

    public RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) {
            return null;
        }
        RandomListNode newHead = new RandomListNode(pHead.label);
        HashMap hashmap = new HashMap<>();
        hashmap.put(pHead, newHead);
        RandomListNode temp_newHead = newHead;
        RandomListNode temp_pHead = pHead.next;
        while (temp_pHead != null) {
            RandomListNode temp = new RandomListNode(temp_pHead.label);
            hashmap.put(temp_pHead, temp);
            temp_newHead.next = temp;
            temp_newHead = temp_newHead.next;
            temp_pHead = temp_pHead.next;
        }
        temp_pHead = pHead;
        while (temp_pHead != null) {
            hashmap.get(temp_pHead).random = hashmap.get(temp_pHead.random);
            temp_pHead = temp_pHead.next;
        }
        return newHead;
    }

}

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

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

转载于:https://www.cnblogs.com/BaoZiY/p/11178211.html