Linked List与Sorting Algorithm结合

OOD与Linked List

<aside> 💡 tips：能不用“global” variable 就不用 “global” variable

java没有真正的“global” variable，这里是指field.

1. Encapsulation and Modularity
2. Code readability and Maintainability
3. Dependency and Side Effects
4. Thread Safety </aside>

Date: March 2, 2023

Topic: Linked list

Recall

Count the length of LinkedList

find the index - k element of it

Find the middle node

Insert element in Linked List

Merge two sorted LinkedList

Delete element in Linked List

Reverse a Linked List

Queue and Stack

Notes

• ListNode cur = head;

• int count = 0;

• for each step: check if cur is not null, count+1, cur move to next ListNode

• TC: O(n), SC: O(1)

• 终止条件：index == k || cur == null

• 循环条件：index != k && cur != null

• TC: O(min(n, k)), SC: O(1)

• Never lose the control of head node, use pointer instead.

• 如果我们需要访问 p.next.next，必须要保证p != null && p.next != null

• 快慢指针法：slow走一步，fast走两步

• 终止条件：奇偶有不同

• cases and stop condition:

• TC: O(n) SC: O(1)

创建dummy node

• 在你不知道对于result LinkedList的头结点是谁时
• dummy node的作用是是代码更简洁，return dummy.next
• 三目运算符：one == null ? true : false
• High Level: 谁小取谁，取谁移谁
• 别忘了移动cur3到新LinkedList的末尾
• TC: O(one.length + two.length) = O(max(one.length, two.length) O(n)
• SC: O(1)

<aside> 📌 SUMMARY:

</aside>

Date: March 25, 2023

Topic: Linked List

<aside> 📌 SUMMARY: LinkedList Reorder， MergeSort一定要记得断开中点和后一个元素。partition记得要curSmall.next = large; curLarge.next = null;

</aside>