LeetCode 劍指offer Q35 複雜連結清單的複制 兩種方式

思路

第一個就是通過使用hash，第二個就是通過在原連結清單的基礎上進行修改。

代碼

package algorithm.jianzhiOffer;

import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

public class Q35 {
    /**
     * 使用hash的非遞歸方式，首先複制節點，并放入hash表。然後在逐個連結next和random
     *
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        if (head == null) return head;
        Map<Node, Node> nodes = new HashMap<>();
        //複制節點
        for (Node cur = head; cur != null; cur = cur.next) {
            nodes.put(cur, new Node(cur.val));
        }
        //安上next和random
        for (Node cur = head; cur != null; cur = cur.next) {
            Node newNode = nodes.get(cur);
            newNode.next = map.get(cur.next);
            newNode.random = map.get(cur.random);
        }

        return map.get(head);
    }

    Map<Node, Node> map = new HashMap<>();

    /**
     * 使用hash的遞歸方式。
     * 同樣的，這裡分成了next和random兩個遞歸分支。
     * 遞歸出口就是hash中已經發現了複制好的節點或者head==null
     * 遞歸式就是若沒有複制好，則進行複制，複制時分别遞歸進入head的next和random進行複制。
     *
     * @param head
     * @return
     */
    public Node copyRandomList1(Node head) {
        if (head == null) return null;
        if (map.containsKey(head)) return map.get(head);
        Node newNode = new Node(head.val);
        map.put(head, newNode);
        newNode.next = copyRandomList1(head.next);
        newNode.random = copyRandomList1(head.random);
        return newNode;
    }

    /**
     * 不使用hash來存放新節點的方式，其實就是換了一個存放新節點的方式。
     * hash因為他鍵值對的存取好處，可以快速定位到每個老節點對應的新節點。
     * 若不使用hash，那該如何綁定新老節點呢，我們可以通過将新節點放在老節點後面的方式來進行綁定。
     *
     * @param head
     * @return
     */
    public Node copyRandomList3(Node head) {
        if (head == null) return null;
        //将複制的節點放在原來每個節點後面
        for (Node cur = head, copy = null; cur != null; cur = cur.next.next) {
            copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
        }

        for (Node cur = head; cur != null; cur = cur.next.next) {
            if(cur.random==null) continue;
            cur.next.random = cur.random.next;
        }
        Node copyHead = head.next;
        Node cur = head;
        Node curCopy = head.next;
        while (cur != null) {
            cur.next = cur.next.next;
            cur = cur.next;
            if (curCopy.next != null) {
                curCopy.next = curCopy.next.next;
                curCopy = curCopy.next;
            }
        }
        //cur=temp;
        return copyHead;
    }
}