138. Copy List with Random Pointer
Tags:
Medium
Skills:
Linked List
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu bạn tạo một bản sao (deep copy) của một linked list mà mỗi node có hai pointer: next và random . Mỗi node mới phải hoàn toàn tách biệt với node cũ nhưng giữ nguyên cấu trúc next và random như ban đầu
Có hai hướng phổ biến
next và random cho node mới dựa vào ánh xạ nàyrandom rồi tách list mới ra khỏi list cũnext giống node cũ (tức là thứ tự các node giống hệt)random trỏ đúng tới node mới tương ứng (tức là nếu node cũ A.random = B thì node mới A'.random = B', chứ không phải trỏ về node B cũ)Tóm lại
Ví dụ trực quan
Giả sử list cũ như sau:
1A (val=1) -> B (val=2) -> C (val=3)
2A.random = C
3B.random = null
4C.random = ABạn phải tạo ra list mới:
1A' (val=1) -> B' (val=2) -> C' (val=3)
2A'.random = C'
3B'.random = null
4C'.random = A'Approach
random , thì node mới (node cũ .next ) sẽ có random là node cũ.random.next Solution
1/**
2 * Definition for _Node.
3 * class _Node {
4 * val: number
5 * next: _Node | null
6 * random: _Node | null
7 *
8 * constructor(val?: number, next?: _Node, random?: _Node) {
9 * this.val = (val===undefined ? 0 : val)
10 * this.next = (next===undefined ? null : next)
11 * this.random = (random===undefined ? null : random)
12 * }
13 * }
14 */
15
16
17function copyRandomList(head: _Node | null): _Node | null {
18 if (!head) return null;
19 let curr: _Node | null = head;
20 while (curr) {
21 const new_node = new _Node(curr.val, curr.next, null);
22 curr.next = new_node;
23 curr = new_node.next;
24 }
25
26 curr = head
27 while (curr) {
28 if (curr.random) {
29 curr.next.random = curr.random.next;
30 }
31 curr = curr.next.next;
32 }
33
34 curr = head;
35 let new_head = head.next;
36 while(curr) {
37 const copy = curr.next;
38 curr.next = copy.next;
39 copy.next = copy.next ? copy.next.next : null
40 curr = curr.next;
41 }
42
43 return new_head;
44};curr.next!.random = curr.random.next; có ý nghĩa như sau:curr là node gốc trong orginal listcurr.next là node mới (copy) vừa được tạo ra và được chèn ngay sao node gốc đó trong danh sách xen kẽ (interleaved list)curr.random là node mà trường random của node gốc trỏ tới (cũng là một node trong danh sách gốc)curr.random.next là node copy tương ứng của node mà curr.random trỏ tới, vì sau bước đầu tiên của thuật toán, mỗi node gốc đề có node copy của nó nằm ngay sauMinh họa:
Giả sử bạn có:
curr là node A (gốc)curr.random là node B (gốc)Khi đó:
curr.next là A'curr.random.next là B'=> curr.next.random = curr.random.next
Tức là: A'.random = B'
Chi tiết hơn
1A (gốc) -> A' (mới) -> B (gốc) -> B' (mới) -> nullA.random = B, thì:A.next là A'A.random là BA.random.next là B' (node copy của B)=> Gán: A'.random = B'
Approach - hashmap
Solution
1/**
2 * Definition for _Node.
3 * class _Node {
4 * val: number
5 * next: _Node | null
6 * random: _Node | null
7 *
8 * constructor(val?: number, next?: _Node, random?: _Node) {
9 * this.val = (val===undefined ? 0 : val)
10 * this.next = (next===undefined ? null : next)
11 * this.random = (random===undefined ? null : random)
12 * }
13 * }
14 */
15
16
17function copyRandomList(head: _Node | null): _Node | null {
18 is(!head) return null;
19 const map: Map<_Node, _Node> = new Map();
20 let curr: _Node | null = head;
21 while(curr) {
22 map.set(curr, new _Node(curr.val));
23 curr = curr.next;
24 }
25
26 curr = head;
27 while(curr) {
28 map.get(curr)!.next = curr.next ? map.get(curr.next) : null;
29 map.get(curr)!.random = curr.random ? map.get(curr.random)! : null;
30 curr =curr.next;
31 }
32
33 return map.get(head)!;
34};