关于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;    }}