Home > Reflections | ⏮️ ⏭️
2024-06-01
🔍 Research
- I want to streamline my process for creating notes for YouTube videos.
- I name all of my note files with only lowercase letters, numbers, and dashes (
/^[a-z0-9-]+/)… aka kabob-case - I use QuickAdd and Templater to create new notes.
- I want to
- provide the name of a video
- have a function format the name according to my file naming scheme
- create a new file with the formatted name
- use the unformatted, provided name as the heading and in various metadata fields
- here’s one post about someone doing something kinda similar that may be helpful
🧠 Education
💡 What Makes Some Brains More Focused Than Others? | Marvin Chun | TEDxKFAS
🏋🏻 Practice
You are given the heads of two sorted linked lists
list1andlist2.Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
/*
Notes:
- lists are sorted in ascending order
- be careful managing cursors and pointers since we're mutating the input
Plan:
1. Initialize empty return value
2. Set up 3 cursors, initialized to the head of each list, one for traversing the result
3. Loop as long as at least one of the cursors is not null
a1. check that our cursors aren't null
a2. If we don't have a return value yet, set it to the smaller of the two & increment that cursor
b. choose which element is <= the other as the next item in our result
c. set the next pointer in our result cursor to this node
4. return the result head
Run-time complexity: O(N) - N = size of both input lists; O(N + M)
Space complexity: O(1) extra space
Test cases
1. [], []
2. [1], []
3. [1, 2], [1]
*/
function mergeTwoLists1(list1: ListNode | null, list2: ListNode | null): ListNode | null {
let result: ListNode | null
// 1. null
// 2. 1 -> null
// 3. 1 -> 2 -> null
let c1: ListNode | null = list1
// 1. null
// 2. null
// 3. 1 -> null
let c2: ListNode | null = list2
let cr: ListNode | null
if (!c1 && !c2) {
// 1. null
result = null
} else if (!c1) {
result = c2
c2 = c2.next
} else if (!c2) {
// 2. 1 -> null
result = c1
// 2. null
c1 = c1.next
} else {
if (c1.val <= c2.val) {
// 3. 1 -> 2 -> null
result = c1
// 3. 2 -> null
c1 = c1.next
} else {
result = c2
c2 = c2.next
}
}
// 1. null
// 2. null
// 3. 1 -> 2 -> null
cr = result
for (; c1 || c2;) {
if (!c1) {
cr.next = c2
c2 = c2.next
} else if (!c2) {
// 3.2 cr = 1 -> 2 -> null
// 3.2 result = 1 -> 1 -> 2 -> null
cr.next = c1
// 3.2 c1 = null
c1 = c1.next
} else if (c1.val <= c2.val) {
cr.next = c1
c1 = c1.next
} else {
// 3.1 cr = 1 -> 1 -> null
cr.next = c2
// 3.1 null
c2 = c2.next
}
// 3.1 cr = 1 -> null
// 3.2 cr = null
cr = cr.next
}
// 1. null
// 2. 1 -> null
// 3. 1 -> 1 -> 2 -> null
return result
}
// simplify: combine initialization and loop
function mergeTwoLists2(list1: ListNode | null, list2: ListNode | null): ListNode | null {
let result: ListNode | null = null
let c1: ListNode | null = list1
let c2: ListNode | null = list2
let cr: ListNode | null = null
let temp: ListNode | null
for (; c1 || c2;) {
if (!c1) {
temp = c2
c2 = c2.next
} else if (!c2) {
temp = c1
c1 = c1.next
} else if (c1.val <= c2.val) {
temp = c1
c1 = c1.next
} else {
temp = c2
c2 = c2.next
}
if (!cr) {
cr = temp
result = cr
} else {
cr.next = temp
cr = cr.next
}
}
return result
}
// simplify: combine null and inequality checks
function mergeTwoLists3(list1: ListNode | null, list2: ListNode | null): ListNode | null {
let result: ListNode | null = null
let c1: ListNode | null = list1
let c2: ListNode | null = list2
let cr: ListNode | null = null
let temp: ListNode | null
for (; c1 || c2;) {
if ((c1?.val || Infinity) <= (c2?.val || Infinity)) {
temp = c1
c1 = c1.next
} else {
temp = c2
c2 = c2.next
}
if (!cr) {
cr = temp
result = cr
} else {
cr.next = temp
cr = cr.next
}
}
return result
}
// simplify: constrain variable scope
function mergeTwoLists4(list1: ListNode | null, list2: ListNode | null): ListNode | null {
let result: ListNode | null = null
for (let c1 = list1, c2 = list2, cr = result; c1 || c2;) {
let temp: ListNode | null
// BUG: val=0 => Infinity
if ((c1?.val || Infinity) <= (c2?.val || Infinity)) {
temp = c1
c1 = c1.next
} else {
temp = c2
c2 = c2.next
}
if (!cr) {
cr = temp
result = cr
} else {
cr.next = temp
cr = cr.next
}
}
return result
}
// simplify: extract helper
const chooseNext = (a: ListNode | null, b: ListNode | null): ListNode | null => {
if (!a) return b
if (!b) return a
return a.val <= b.val ? a : b
}
function mergeTwoLists5(list1: ListNode | null, list2: ListNode | null): ListNode | null {
let result: ListNode | null = null
for (let c1 = list1, c2 = list2, cr = result; c1 || c2;) {
const temp = chooseNext(c1, c2)
if (temp === c1) {
c1 = c1.next
} else {
c2 = c2.next
}
if (!cr) {
cr = temp
result = cr
} else {
cr.next = temp
cr = cr.next
}
}
return result
}
// simplify: eliminate unnecessary temp variable; initialize result at declaration
function mergeTwoLists6(list1: ListNode | null, list2: ListNode | null): ListNode | null {
const result = chooseNext(list1, list2)
for (let c1 = list1, c2 = list2, cr = result; c1 || c2;) {
if (cr === c1) {
c1 = c1.next
} else {
c2 = c2.next
}
cr.next = chooseNext(c1, c2)
cr = cr.next
}
return result
}
// annotate with test cases
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
// 1. list1=[] list2=[]
// 2. list1=[1] list2=[]
// 3. list1=[] list2=[3]
// 4. list1=[4,6] list2=[2,5]
const result = chooseNext(list1, list2)
// 1. result=[]
// 2. result=[1]
// 3. result=[3]
// 4. result=[2,5]
for (let c1 = list1, c2 = list2, cr = result; c1 || c2;) {
// 2. c1=[1] c2=[] cr=[1]
// 3. c1=[] c2=[3] cr=[3]
// 4.1 c1=[4,6] c2=[2,5] cr=[2,5]
if (cr === c1) {
c1 = c1.next
// 2. c1=[]
// 4.2 c1=[6]
// 4.4 c1=[]
} else {
c2 = c2.next
// 3. c2=[]
// 4.1 c2=[5]
// 4.3 c2=[]
}
cr.next = chooseNext(c1, c2)
// 2. cr=[1] result=[1]
// 3. cr=[3] result=[3]
// 4.1 cr=[2,4] result=[2,4]
// 4.2 cr=[4,5] result=[2,4,5]
// 4.3 cr=[5,6] result=[2,4,5,6]
// 4.4 cr=[6] result=[2,4,5,6]
cr = cr.next
// 2. cr=[]
// 3. cr=[]
// 4.1 cr=[4,6] result=[2,4,6]
// 4.2 cr=[5] result=[2,4,5]
// 4.3 cr=[6] result=[2,4,5,6]
// 4.4 cr=[] result=[2,4,5,6]
}
return result
// 1. result=[]
// 2. result=[1]
// 3. result=[3]
// 4. result=[2,4,5,6]
}
// we can eliminate the 3rd cursor but it's harder to follow and requires a new temp variable
function mergeTwoListsAlt(list1: ListNode | null, list2: ListNode | null): ListNode | null {
const result = chooseNext(list1, list2)
for (let c1 = result, c2 = list1 === result ? list2 : list1; c2;) {
if (chooseNext(c1.next, c2) === c1.next) {
c1 = c1.next
} else {
const temp = c1.next
c1.next = c2
c2 = temp
}
}
return result
}