Gidhub BE Developer

LeetCode : 138. Copy List with Random Pointer

2021-02-06
goodGid

138. Copy List with Random Pointer

Problem

• Need to Retry
``````Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
``````

Example

• See the Problem

[1] Code (21. 02. 06)

``````class Solution {

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

while (cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}

while (cur != null) {
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}

}
}
``````
• 아이디어 싸움인데 졌다.

심플하면서도 깔끔한 아이디어이다.

• map.get(XXX) = 동일한 값을 갖고 있는 Copied Node 라고 생각하면 된다.

• 마지막에 return map.get(cur); 로 제출을 해서 자꾸 뭐가 틀렸지 고민하게 만들었다.

그냥 실수였다.

[2] Code (21. 02. 06)

``````public Node copyRandomList(Node head) {
if (head == null) { // [1]
return null;
}

// val와 next 값 설정
while (cur != null) {
Node next = cur.next;
Node copyNode = new Node(cur.val);
copyNode.next = next;
cur.next = copyNode;
cur = next;
}

// random 값 설정
while (cur != null) {
Node copyNode = cur.next;
if (cur.random != null) {
copyNode.random = cur.random.next;
}
cur = cur.next.next;
}

Node copyNode;
while (cur != null) {
Node nextNode = cur.next.next;
copyNode = cur.next;

cur.next = nextNode;
if (nextNode != null) {
copyNode.next = nextNode.next;
}
cur = nextNode;
}

}
``````
• [1] : [1] 코드가 없으면 [2]에서 NPE가 발생한다.

• 아이디어를 이해하는 건 어렵지 않았는데

직접 구현하는 게 생각보다 오래 걸렸다.