Xinrui's personal website that shares my work and thoughts
Hi, I’m William Lina
Explore the professional journey, expertise, and achievements of a dedicated medical practitioner. Discover education, experience, clinical skills, research, and patient care .
Special Facilities For Our Patients
Rehabilitation Retreat
A serene haven dedicated to physical and emotional recovery, providing specialized therapies.
Adventure Basecamp
An adventure facility providing equipment, training, and guided experiences.
Child Development
A nurturing environment for children's growth and learning, equipped with a range of developmental programs.
Dr. Laura Jerry
Dr. Laura Jerry brings a wealth of experience and expertise to her practice. With a focus on patient-centered care, she is known for her warm and empathetic approach, always taking the time to listen to her patients’ concerns. Her extensive medical knowledge and dedication to staying at the forefront of the field make her a trusted healthcare partner.
Explore the range of medical services Dr. Collins offers, including general check-ups, preventative care, chronic disease management, and more. She is committed to working with you to develop personalized treatment plans that suit your unique needs.
Services For You &
Your Family
Pediatric Healthcare
Your first line of defense in health. Our primary care services cover check-ups and vaccinations.
Specialist Care
Access to top medical specialists for in-depth evaluation and treatment of specific health conditions.
Women's Health
Tailored healthcare services for women, including gynecology, obstetrics, and reproductive health.
Geriatric Care
Specialized care for our senior patients, focusing on age-related health issues chronic disease.
Diagnostic Testing
State-of-the-art diagnostic services, including imaging, laboratory tests, and screenings
Testimonial
Nevine Acotanza
Chief Operating OfficerChief Operating Officer
Mar 4, 2015 - Aug 30, 2021 testMr. Lee displayed remarkable responsiveness, professionalism, expertise, and proficiency. He swiftly grasped the intended concept and guided me in creating an elegant and captivating presentation.
Jone Duone Joe
Operating OfficerOperating Officer
Mar 4, 2016 - Aug 30, 2021Sarah exhibited remarkable responsiveness, professionalism, knowledge, and expertise. She quickly understood the intended concept and guided me in creating a sleek and aesthetically pleasing presentation.
Nevine Dhawan
CEO Of OfficerCEO Of Officer
Mar 4, 2016 - Aug 30, 2021Maecenas finibus nec sem ut imperdiet. Ut tincidunt est ac dolor aliquam sodales. Phasellus sed mauris hendrerit, laoreet sem in, lobortis mauris hendrerit ante. Ut tincidunt est ac dolor aliquam sodales phasellus smauris
My Regular Scedule
Medical Diagnosis Treatment
- Address: Google Out Tech - (2017 - Present)
- Working Days: Monday, Wednesday, Saturday
- Visiting Hour: 9am - 4pm
- Contact No: +44 0015454500
Medical Diagnosis Treatment
- Address: Google Out Tech - (2017 - Present)
- Working Days: Monday, Wednesday, Saturday
- Visiting Hour: 9am - 4pm
- Contact No: +44 0015454500
Medical Diagnosis Treatment
- Address: Google Out Tech - (2017 - Present)
- Working Days: Monday, Wednesday, Saturday
- Visiting Hour: 9am - 4pm
- Contact No: +44 0015454500
Medical Diagnosis Treatment
- Address: Google Out Tech - (2017 - Present)
- Working Days: Monday, Wednesday, Saturday
- Visiting Hour: 9am - 4pm
- Contact No: +44 0015454500
Latest News
Implementing a Priority Queue in TypeScript: A Step-by-Step Guide
Priority queues are essential data structures in computer science, especially when dealing with tasks that require ordering based on priority. In this blog post, we’ll explore how to implement a priority queue in TypeScript, which can help solve problems like LeetCode’s 215. Kth Largest Element in an Array.
Introduction
A priority queue is a special type of queue where each element is associated with a priority, and elements are served based on their priority. The higher the priority, the sooner the element is dequeued. We’ll implement a min-heap-based priority queue, which ensures that the element with the smallest value (highest priority) is always at the front.
Why TypeScript?
TypeScript adds static typing to JavaScript, providing better tooling and error checking at compile time. This makes our code more robust and maintainable.
Step 1: Define the Priority Queue Class
First, let’s create a PriorityQueue
class that will hold our heap.
class PriorityQueue<T> {
private heap: T[] = [];
constructor(private comparator: (a: T, b: T) => number) {}
}
- heap: An array representing the binary heap.
- comparator: A function to compare two elements, defining the priority.
Step 2: Implement the Helper Methods
Swap Method
We need a method to swap two elements in the heap.
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
Parent and Child Index Methods
Calculate the indices of parent and child nodes.
private parentIndex(index: number): number {
return Math.floor((index - 1) / 2);
}
private leftChildIndex(index: number): number {
return 2 * index + 1;
}
private rightChildIndex(index: number): number {
return 2 * index + 2;
}
Step 3: Implement the Push Method
Add a new element to the heap and reorder it to maintain the heap property.
push(item: T): void {
this.heap.push(item);
this.heapifyUp();
}
Heapify Up
Move the new element up to its correct position.
private heapifyUp(): void {
let index = this.heap.length - 1;
while (
index > 0 &&
this.comparator(this.heap[index], this.heap[this.parentIndex(index)]) < 0
) {
this.swap(index, this.parentIndex(index));
index = this.parentIndex(index);
}
}
Step 4: Implement the Pop Method
Remove and return the element with the highest priority.
pop(): T | undefined {
if (this.heap.length === 0) return undefined;
if (this.heap.length === 1) return this.heap.pop();
const item = this.heap[0];
this.heap[0] = this.heap.pop() as T;
this.heapifyDown();
return item;
}
Heapify Down
Reorder the heap after removing the root element.
private heapifyDown(): void {
let index = 0;
const length = this.heap.length;
while (this.leftChildIndex(index) < length) {
let smallestChildIndex = this.leftChildIndex(index);
const rightChildIdx = this.rightChildIndex(index);
if (
rightChildIdx < length &&
this.comparator(this.heap[rightChildIdx], this.heap[smallestChildIndex]) < 0
) {
smallestChildIndex = rightChildIdx;
}
if (
this.comparator(this.heap[index], this.heap[smallestChildIndex]) <= 0
) {
break;
}
this.swap(index, smallestChildIndex);
index = smallestChildIndex;
}
}
Step 5: Implement Peek and Size Methods
Get the element with the highest priority without removing it and get the size of the queue.
peek(): T | undefined {
return this.heap[0];
}
size(): number {
return this.heap.length;
}
Step 6: Implement the Update Method
Now, we’ll implement an update()
method that allows us to update the priority of an element, either by its index or by its value.
Update by Index
updateAt(index: number, newValue: T): void {
if (index < 0 || index >= this.heap.length) {
throw new Error("Index out of bounds");
}
const oldValue = this.heap[index];
this.heap[index] = newValue;
if (this.comparator(newValue, oldValue) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
Explanation: We replace the value at the given index with the new value. Then, depending on how the new value compares to the old value, we either heapify up or heapify down to restore the heap property.
Update by Value
Since updating by value can be inefficient (as it may require searching the entire heap), we’ll implement it cautiously.
update(value: T, newValue: T): void {
const index = this.heap.findIndex((element) => element === value);
if (index === -1) {
throw new Error("Value not found in heap");
}
this.updateAt(index, newValue);
}
Explanation: We find the index of the value in the heap and then call updateAt()
to update it.
Remove and Remove By Index
public remove(item: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.removeAtIndex(index);
}
private removeAtIndex(index: number): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
if (index === this.heap.length - 1) {
this.heap.pop();
} else {
this.heap[index] = this.heap.pop() as T;
const parentIndex = this.parent(index);
if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
}
Step 7: Implement the Heapify Function
We’ll add a heapify()
method to build a heap from an existing array.
heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.heapifyDown(i);
}
}
Step 8: Use the Priority Queue to Solve LeetCode 215
Now, let’s use our PriorityQueue
to find the Kth largest element in an array.
Problem Statement
Given an integer array nums
and an integer k
, return the kth
largest element in the array.
Solution
We’ll use a min-heap (priority queue) to keep track of the largest k
elements.
function findKthLargest(nums: number[], k: number): number {
const pq = new PriorityQueue<number>((a, b) => a - b);
for (const num of nums) {
pq.push(num);
if (pq.size() > k) {
pq.pop();
}
}
return pq.peek() as number;
}
Comparator: (a, b) => a - b
ensures a min-heap.
Logic: Maintain a heap of size k
. The root will be the kth largest element.
Full Code Listing with small changes in variable names
class PriorityQueue<T> {
private heap: T[];
constructor(private compare: (a: T, b: T) => number) {
this.heap = [];
}
private swap(i: number, j: number): void {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
}
private parent(i: number): number {
return Math.floor((i - 1) / 2);
}
private left(i: number): number {
return 2 * i + 1;
}
private right(i: number): number {
return 2 * i + 2;
}
private heapifyUp(index: number): void {
while (index > 0 && this.compare(this.heap[index], this.heap[this.parent(index)]) < 0) {
this.swap(index, this.parent(index));
index = this.parent(index);
}
}
private heapifyDown(index: number): void {
const length = this.heap.length;
while (this.left(index) < length) {
let smallest = this.left(index);
const rightIndex = this.right(index);
if (rightIndex < length && this.compare(this.heap[rightIndex], this.heap[smallest]) < 0) {
smallest = rightIndex;
}
if (this.compare(this.heap[index], this.heap[smallest]) < 0) {
break;
}
this.swap(index, smallest);
index = smallest;
}
}
public push(item: T): void {
this.heap.push(item);
this.heapifyUp(this.heap.length - 1);
}
public pop(): T | undefined {
if (this.heap.length === 0) return undefined;
if (this.heap.length === 1) return this.heap.pop();
const root = this.heap[0];
this.heap[0] = this.heap.pop() as T;
this.heapifyDown(0);
return root;
}
public peek(): T | undefined {
return this.heap[0];
}
public size(): number {
return this.heap.length;
}
public updateAtIndex(index: number, newItem: T): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
this.heap[index] = newItem;
if (this.compare(newItem, this.heap[this.parent(index)]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
public update(item: T, newItem: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.updateAtIndex(index, newItem);
}
public remove(item: T): void {
const index = this.heap.indexOf(item);
if (index === -1) {
throw new Error('item not found');
}
this.removeAtIndex(index);
}
private removeAtIndex(index: number): void {
if (index < 0 || index >= this.heap.length) {
throw new Error('index out of bounds');
}
if (index === this.heap.length - 1) {
this.heap.pop();
} else {
this.heap[index] = this.heap.pop() as T;
const parentIndex = this.parent(index);
if (index > 0 && this.compare(this.heap[index], this.heap[parentIndex]) < 0) {
this.heapifyUp(index);
} else {
this.heapifyDown(index);
}
}
}
public isEmpty(): boolean {
return this.heap.length === 0;
}
public heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2); i >= 0; i--) {
this.heapifyDown(i);
}
}
}
Testing the Solution
Let’s test our implementation with an example.
const nums = [3, 2, 1, 5, 6, 4];
const k = 2;
const result = findKthLargest(nums, k);
console.log(`The ${k}th largest element is ${result}`); // Output: 5
Testing the Update and Heapify Methods
Using heapify()
to Build a Heap from an Array
typescriptCopy codeconst nums = [3, 2, 1, 5, 6, 4];
const pq = new PriorityQueue<number>((a, b) => a - b);
pq.heapify(nums);
console.log(pq.peek()); // Output: 1
Rewriting the findKthLargest
Function Using heapify()
We can optimize our earlier findKthLargest
function by using heapify()
.
function findKthLargest(nums: number[], k: number): number {
const pq = new PriorityQueue<number>((a, b) => b - a); // Max-heap
pq.heapify(nums);
for (let i = 0; i < k - 1; i++) {
pq.pop();
}
return pq.peek() as number;
}
Why Use heapifyDown()
in heapify()
?
That’s a great question! In the heapify()
method, we use heapifyDown()
instead of heapifyUp()
because when building a heap from an existing array, we need an efficient way to ensure the heap property is maintained throughout the structure.
When constructing a heap from an unordered array, the most efficient method is to start from the last non-leaf node and move upwards, performing heapifyDown()
on each node. This process is known as the heapify algorithm or build heap.
Reasons:
- Higher Efficiency:
- Lower Time Complexity: Using
heapifyDown()
, the overall time complexity of building the heap is O(n). If we were to useheapifyUp()
, the time complexity would increase to O(n log n) in the worst case. - Fewer Node Movements:
heapifyDown()
can fix all violations of the heap property from the current node down to the leaves in one pass, whereasheapifyUp()
might require multiple passes for each node.
- Lower Time Complexity: Using
- Suitable for Building the Entire Heap:
heapifyDown()
is more appropriate when you need to adjust the heap starting from the internal nodes downwards.heapifyUp()
is typically used when inserting a new element into an already built heap.
Detailed Explanation
When building a heap, our goal is to ensure that every parent node satisfies the heap property with respect to its children (for a min-heap, each parent node is less than or equal to its children). To achieve this efficiently, we start from the last non-leaf node because leaf nodes are already valid heaps by themselves.
heapify(array: T[]): void {
this.heap = array;
for (let i = Math.floor(this.heap.length / 2) - 1; i >= 0; i--) {
this.heapifyDown(i);
}
}
- Calculating the Starting Index:
Math.floor(this.heap.length / 2) - 1
- This formula gives us the index of the last non-leaf node.
- In a binary heap, nodes with indices from
Math.floor(n/2)
ton - 1
are all leaf nodes.
- Why Not Use
heapifyUp()
?heapifyUp()
is suitable for situations where you’re adding a single new element to the heap and need to adjust its position.- Using
heapifyUp()
during the heap construction process would result in higher time complexity because each node might need to be moved up multiple levels. - In contrast,
heapifyDown()
can adjust the subtree rooted at a node in one pass.
An Example
Suppose we have an array [3, 2, 1, 5, 6, 4]
and we want to build a min-heap.
- Initialize the Heap:typescriptCopy code
this.heap = [3, 2, 1, 5, 6, 4];
- Start from the Last Non-Leaf Node:
- The array length is 6, so the index of the last non-leaf node is
Math.floor(6 / 2) - 1 = 2
.
- The array length is 6, so the index of the last non-leaf node is
- Perform
heapifyDown()
on Index 2:- The node at index 2 has a value
1
, and its children are out of bounds, so no action is needed.
- The node at index 2 has a value
- Perform
heapifyDown()
on Index 1:- The node at index 1 has a value
2
, with left child5
and right child6
. - Since
2
is less than its children, no action is needed.
- The node at index 1 has a value
- Perform
heapifyDown()
on Index 0:- The node at index 0 has a value
3
, with left child2
and right child1
.The right child1
is the smallest, so we swap3
with1
.
- The heap now looks like
[1, 2, 3, 5, 6, 4]
.
- The node at index 0 has a value
- Continue
heapifyDown()
on the Swapped Node:- The node at index 2 (now with value
3
) has a left child4
, but since3
is less than4
, no further action is needed.
- The node at index 2 (now with value
Summary
- Using
heapifyDown()
:- Ideal for building a heap from an array.
- Overall time complexity is O(n).
- Using
heapifyUp()
:- Suitable for inserting a single element into an existing heap.
- Each insertion has a time complexity of O(log n).
Therefore, in the heapify()
method, we choose heapifyDown()
to efficiently build a valid heap from the bottom up.
Additional Notes
- Why Not Use
heapifyUp()
?- If we used
heapifyUp()
on each node starting from the root, each node might have to move up several levels, leading to higher overall time complexity. heapifyDown()
allows us to fix violations of the heap property starting from each internal node down to the leaves in a single pass.
- If we used
- Time Complexity Comparison:
- Using
heapifyDown()
: Total time complexity is O(n). - Using
heapifyUp()
: Total time complexity is O(n log n).
- Using
Conclusion
We’ve successfully implemented a priority queue in TypeScript using a min-heap and applied it to solve a common algorithm problem. This implementation can be extended or modified for other use cases, such as max-heaps or custom priority criteria.
References
使用TypeScript实现优先队列 (Priority Queue)
使用TypeScript实现优先队列 (Priority Queue)
前言
大家好!今天我想和大家分享如何使用TypeScript实现一个优先队列(Priority Queue),并利用它来解决LeetCode第215题——数组中的第K个最大元素。在算法面试中,优先队列是一个非常常用的数据结构,理解并能熟练实现它对我们解决一系列问题都有帮助。
问题描述
LeetCode第215题:数组中的第K个最大元素
给定一个未排序的整数数组 nums
,找到其中第 k
个最大的元素。
示例:
输入: nums = [3,2,1,5,6,4], k = 2
输出: 5
输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示:
- 1 ≤ k ≤ nums.length ≤ 10^4
- -10^4 ≤ nums[i] ≤ 10^4
解题思路
要找到第 k
个最大的元素,我们可以采用多种方法:
- 排序法:将数组排序,然后取第
k
个最大的元素。时间复杂度为 O(n log n)。 - 基于堆的优先队列:使用一个大小为
k
的最小堆来维护当前最大的k
个元素。时间复杂度为 O(n log k)。 - 快速选择算法:类似快速排序的分区思想,平均时间复杂度为 O(n)。
在这篇文章中,我们重点介绍使用最小堆实现的优先队列,因为它在实际应用中非常高效,且实现相对简单。
什么是优先队列?
优先队列是一种特殊的队列,元素按照优先级进行出入队操作。常用的实现方式是堆,根据堆的性质,可以快速地获取当前的最值(最大值或最小值)。
在我们的问题中,我们需要维护一个大小为 k
的最小堆,堆顶元素就是当前第 k
个最大的元素。
TypeScript中实现最小堆
堆的基本操作
- 插入元素(insert):将新元素添加到堆的末尾,然后向上调整位置(上浮)。
- 删除堆顶元素(extractMin):移除堆顶元素,将末尾元素放到堆顶,然后向下调整位置(下沉)。
- 查看堆顶元素(getMin):获取堆顶元素的值。
- 获取堆的大小(size):返回堆中元素的数量。
实现代码
class MinHeap {
private heap: number[] = [];
insert(val: number): void {
this.heap.push(val);
this.bubbleUp();
}
private bubbleUp(): void {
let index = this.heap.length - 1;
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[index] >= this.heap[parentIndex]) break;
[this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
index = parentIndex;
}
}
extractMin(): number | undefined {
if (this.heap.length === 0) return undefined;
const min = this.heap[0];
const end = this.heap.pop()!;
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown();
}
return min;
}
private sinkDown(): void {
let index = 0;
const length = this.heap.length;
const element = this.heap[0];
while (true) {
let leftChildIdx = 2 * index + 1;
let rightChildIdx = 2 * index + 2;
let swapIdx: number | null = null;
if (leftChildIdx < length) {
if (this.heap[leftChildIdx] < element) {
swapIdx = leftChildIdx;
}
}
if (rightChildIdx < length) {
if (
(swapIdx === null && this.heap[rightChildIdx] < element) ||
(swapIdx !== null && this.heap[rightChildIdx] < this.heap[leftChildIdx])
) {
swapIdx = rightChildIdx;
}
}
if (swapIdx === null) break;
[this.heap[index], this.heap[swapIdx]] = [this.heap[swapIdx], this.heap[index]];
index = swapIdx;
}
}
getMin(): number | undefined {
return this.heap[0];
}
size(): number {
return this.heap.length;
}
}
代码解释
- insert(val: number):将元素添加到堆末尾,然后调用
bubbleUp
进行上浮操作,保持最小堆性质。 - bubbleUp():从新添加的元素开始,与父节点比较,如果小于父节点则交换位置,直到满足最小堆性质。
- extractMin():移除并返回堆顶元素,将堆末尾元素放到堆顶,然后调用
sinkDown
进行下沉操作。 - sinkDown():从堆顶开始,与子节点比较,如果大于子节点则交换位置,直到满足最小堆性质。
- getMin():返回堆顶元素,不修改堆。
- size():返回堆中元素的数量。
利用最小堆解决第K个最大元素问题
实现思路
- 创建一个大小为
k
的最小堆。 - 遍历数组,将元素逐一插入堆中。
- 当堆的大小超过
k
时,移除堆顶元素(最小值)。 - 遍历完成后,堆顶元素就是第
k
个最大元素。
实现代码
function findKthLargest(nums: number[], k: number): number {
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.insert(num);
if (minHeap.size() > k) {
minHeap.extractMin();
}
}
return minHeap.getMin()!;
}
代码解释
- 遍历数组:将每个元素插入到最小堆中。
- 维护堆的大小:如果堆的大小超过
k
,则移除堆顶元素,确保堆中始终只包含当前最大的k
个元素。 - 返回结果:遍历结束后,堆顶元素即为第
k
个最大元素。
测试代码
const nums1 = [3, 2, 1, 5, 6, 4];
const k1 = 2;
console.log(findKthLargest(nums1, k1)); // 输出: 5
const nums2 = [3, 2, 3, 1, 2, 4, 5, 5, 6];
const k2 = 4;
console.log(findKthLargest(nums2, k2)); // 输出: 4
时间复杂度分析
- 插入和移除操作:每次操作的时间复杂度为 O(log k)。
- 总时间复杂度:对于长度为
n
的数组,总的时间复杂度为 O(n log k),当k
远小于n
时,效率较高。
空间复杂度分析
- 空间复杂度:使用了额外的堆空间,最大为 O(k)。
总结
通过使用最小堆实现的优先队列,我们可以高效地找到数组中的第 k
个最大元素。这种方法在处理大规模数据时非常实用,因为我们不需要对整个数组进行排序,只需维护一个大小为 k
的堆即可。
优点
- 高效性:时间复杂度为 O(n log k),比直接排序的 O(n log n) 更优。
- 适用性强:当需要实时处理数据流并获取第
k
个最大元素时,此方法非常适用。
缺点
- 实现复杂度:相比内置排序函数,手动实现堆需要更多的代码和调试。
后记
希望这篇文章能帮助大家理解如何在TypeScript中实现优先队列,并应用于实际问题。如果有任何疑问或改进建议,欢迎在评论区与我交流!
参考资料
感谢阅读!如果觉得有帮助,请点赞支持。
430. Flatten a Multilevel Doubly Linked List
You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.
Given the head
of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr
be a node with a child list. The nodes in the child list should appear after curr
and before curr.next
in the flattened list.
Return the head
of the flattened list. The nodes in the list must have all of their child pointers set to null
.
Example 1:
Input: head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12] Output: [1,2,3,7,8,11,12,9,10,4,5,6] Explanation: The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes:
Example 2:
Input: head = [1,2,null,3] Output: [1,3,2] Explanation: The multilevel linked list in the input is shown. After flattening the multilevel linked list it becomes:
Example 3:
Input: head = [] Output: [] Explanation: There could be empty list in the input.
Constraints:
- The number of Nodes will not exceed
1000
. 1 <= Node.val <= 105
How the multilevel linked list is represented in test cases:
We use the multilevel linked list from Example 1 above:
1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULL
The serialization of each level is as follows:
[1,2,3,4,5,6,null] [7,8,9,10,null] [11,12,null]
To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:
[1, 2, 3, 4, 5, 6, null] | [null, null, 7, 8, 9, 10, null] | [ null, 11, 12, null]
Merging the serialization of each level and removing trailing nulls we obtain:
[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
Problem Explanation
The goal is to flatten a multilevel doubly linked list. Each node has next
, prev
, and child
pointers. The child
pointer points to another doubly linked list, which might have its own child
pointers. We need to flatten this structure into a single-level doubly linked list.
Approach
- Traverse the linked list using a pointer
current
. - Whenever we encounter a node with a
child
, we need to:- Temporarily store the
next
node. - Flatten the
child
list recursively. - Insert the flattened
child
list between the current node and the next node. - Update all the necessary pointers (
next
andprev
). - Ensure the
child
pointer is set tonull
.
- Temporarily store the
- Continue this process until the entire list is flattened.
Code with Detailed Comments
var flatten = function(head) {
if (head === null) return null;
// Start traversing from the head node
let current = head;
// Traverse the entire linked list
while (current !== null) {
// If the current node has a child, we need to flatten it
if (current.child !== null) {
// Store the next node temporarily
let next = current.next;
// Recursively flatten the child list
let child = flatten(current.child);
// Insert the flattened child list
current.next = child;
child.prev = current;
// Find the tail of the flattened child list
while (child.next !== null) {
child = child.next;
}
// Connect the tail of the flattened child list to the next node
if (next !== null) {
next.prev = child;
}
child.next = next;
// Remove the child pointer
current.child = null;
}
// Move to the next node
current = current.next;
}
return head;
};
Step-by-Step Explanation
- Initialization:
- Check if
head
isnull
. If it is, returnnull
immediately. - Initialize
current
to start from thehead
node.
- Check if
- Traversal:
- Use a
while
loop to traverse the entire linked list.
- Use a
- Handling the
child
:- If
current
has achild
, perform the following steps:- Temporarily store the
next
node (current.next
). - Recursively flatten the
child
list by callingflatten(current.child)
. - Insert the flattened
child
list between thecurrent
node and thenext
node:- Set
current.next
to the head of the flattenedchild
list. - Update the
prev
pointer of the flattenedchild
list head to point tocurrent
.
- Set
- Find the tail of the flattened
child
list by iterating through it untilchild.next
isnull
. - Connect the tail of the flattened
child
list to thenext
node:- Set
next.prev
to the tail of the flattenedchild
list (ifnext
is notnull
). - Set the
next
pointer of the tail of the flattenedchild
list tonext
.
- Set
- Set
current.child
tonull
as it is now flattened and integrated into the main list.
- Temporarily store the
- If
- Continue Traversal:
- Move
current
to the next node (current.next
) and repeat the process until the end of the list is reached.
- Move
Complexity Analysis
- Time Complexity: O(n), where n is the total number of nodes in the list. Each node is processed once, and the child lists are flattened and inserted in linear time.
- Space Complexity: O(d), where d is the maximum depth of the multilevel list. This space is used by the recursion stack due to the depth-first search approach.
This approach ensures that all pointers are correctly updated, maintaining the doubly linked structure while flattening the multilevel list into a single-level list.