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