Sword finger offer | interview question 28: copy linked list

Knock algorithm series articles

"Leetcode : https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof

"GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_28_copyRandomList/Solution.java

Sword finger Offer 28 Replication of complex linked list

Title Description: please implement the copyRandomList function to copy a complex linked list. In a complex linked list, each node has a next pointer to the next node and a random pointer to any node or null in the linked list.

Difficulty: medium

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output:[[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output:[[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output:[[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output:[]
Explanation: the given linked list is null (null pointer), so it returns null.

Tips:

10000 <= Node.val <= 10000
Node.random is empty (null) or points to a node in the linked list.
The number of nodes shall not exceed 1000.

Method: hash table

"Using the query characteristics of the hash table, consider building the key value pair mapping relationship between the original linked list node and the corresponding node of the new linked list, and then traverse the next and random reference points of each node of the new linked list.

Algorithm flow:

If the header node head is empty, null is returned directly;
Initialization: hash table dic, node cur points to the header node;
Copy linked list:
1. Create a new node and add key value pairs to dic (original cur node, new cur node);
2. cur traverses to the next node in the original linked list;
The reference to build a new linked list points to:
1. Build the next and random bow of the new node, and point to it;
2. cur traverses to the next node in the original linked list;
Return value: the header node dic[cur] of the new linked list;

Complexity analysis:

Time complexity O(N): traverse the linked list in two rounds, using O(N) time.
Space complexity 0(N): hash table dic uses extra space of linear size.

package com.nateshao.sword_offer.topic_28_copyRandomList;

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

/**
 * @date Created by Shao Tongjie on 2021/12/2 14:05
 * @WeChat official account programmers
 * @Personal website www.nateshao.com cn
 * @Blog https://nateshao.gitee.io
 * @GitHub https://github.com/nateshao
 * @Gitee https://gitee.com/nateshao
 * Description:  Replication of complex linked list
 */
public class Solution {
    /**
     * Selected answers
     * @param head
     * @return
     */
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        // 3. Copy each node and create a Map mapping of "original node - > new node"
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        // 4. Build the next and random points of the new linked list
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        // 5. Return the header node of the new linked list
        return map.get(head);
    }


    /**
     * Idea: first copy the next node of the linked list, connect the copied node to the original node, and then copy other nodes
     * Node, and finally take the node with even position (copied node).
     *
     * @param head
     * @return
     */
    public Node copyRandomList2(Node head) {
        if (head == null) return null;
        Node node = new Node(head.val);
        Node temp = node;

        while (head.next != null) {
            temp.next = new Node(head.next.val);
            if (head.random != null) {
                temp.random = new Node(head.random.val);
            }
            head = head.next;
            temp = temp.next;
        }
        return head;
    }

    // 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;
        }
    }
}

Reference link: https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/solution/jian-zhi-offer-35-fu-za-lian-biao-de-fu-zhi-ha-xi-

Added by Crys on Wed, 29 Dec 2021 13:01:24 +0200

Programming VIP

Sword finger offer | interview question 28: copy linked list

Sword finger Offer 28 Replication of complex linked list

Method: hash table

Popular Keywords