关于java:offer-35-复杂链表的赋值

简单链表的赋值

题目剖析

一般链表的节点定义如下：

// Definition for a Node.
class Node {
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
        this.next = null;
    }
}

本题链表的节点的定义如下
比一般的链表多了一个random

// Definition for a Node.
class Node {
    int val;
    Node next, random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

就是在复制链表的时候还要带着random

这个时一般链表的复制

class Solution {
    public Node copyRandomList(Node head) {
        Node cur = head;
        Node dum = new Node(0), pre = dum;
        while(cur != null) {
            Node node = new Node(cur.val); // 复制节点 cur
            pre.next = node;               // 新链表的 前驱节点 -> 以后节点
            // pre.random = "???";         // 新链表的 「 前驱节点 -> 以后节点 」 无奈确定
            cur = cur.next;                // 遍历下一节点
            pre = node;                    // 保留以后新节点
        }
        return dum.next;
    }
}

利用哈希表查表

HashMap 的键值对，构建原来的链表节点和新链表的对应节点的键值对映射关系，而后再遍历next和random援用指向

拼接 + 拆分

也就是构建新的链表为
node1→node1new→node2→node2 new→⋯
因而当node1指向node2的时候node1new也指向node2new，node1的random指向本人的random的时候，那node1new的random也就只想node1.random.next

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head==null) return null;
        //首先定义旧链表的头节点 
        Node cur = head;
        //复制各个节点形成拼接链表
        while(cur!=null){
            Node temp = new Node(cur.val);
            //新链表节点的next是以后节点的next
            temp.next = cur.next;
            //以后节点的next是新节点
            cur.next  = temp;
            //持续便当，下一个节点应该是以后节点的next的next，也就是temp的next
            cur = temp.next;
        }
        //对新拼接的链表设置random指向
        cur = head;
        while(cur!=null){
            if(cur.random!=null){
                //下一个节点也就是新节点的随机等于以后旧节点的随机的next
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //指向结束 对链表进行拆分 间接拿头节点的next就是新链表的头节点
        cur = head.next;
        Node res = head.next;
        Node pre = head;
        while(cur.next!=null){
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;//旧链表
            cur = cur.next;//新链表
        }
        //执行结束之后，旧链表还差一个尾节点的next的null没加 
        //因为他原本的next应该是新链表，然而拆开之后就变成null了
        pre.next = null;
        return res;
    }
}