一个认为一切根源都是“自己不够强”的INTJ
个人主页：用哲学编程-CSDN博客专栏：每日一题——举一反三
Python编程学习
Python内置函数
Python-3.12.0文档解读
题目链接
目录
我的写法
C嘎嘎
编辑
Python
代码点评
代码点评
时间复杂度分析
空间复杂度分析
改进建议
我要更强
哲学和编程思想
举一反三
1. 模块化思维
2. 抽象与封装
3. 迭代与增量开发
4. 避免副作用
5. 优化与性能
我的写法
C嘎嘎
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// 创建两个链表的头指针，分别用于存储小于x和大于等于x的节点
ListNode* listLessThanX = pHead, *listEqualOrGreaterThanX = pHead;
// 1. 找到listLessThanX和listEqualOrGreaterThanX的首元素，cur1,cur2将始终分别指向前两者当前最后一个元素
for (; listLessThanX;) {
if (listLessThanX->val < x) {
break; // 找到小于x的节点，跳出循环
} else {
listLessThanX = listLessThanX->next; // 继续寻找
}
}
for (; listEqualOrGreaterThanX;) {
if (listEqualOrGreaterThanX->val >= x) {
break; // 找到大于等于x的节点，跳出循环
} else {
listEqualOrGreaterThanX = listEqualOrGreaterThanX->next; // 继续寻找
}
}
// 检查是否找到了小于x和大于等于x的节点
if (listLessThanX == NULL && listEqualOrGreaterThanX)
return pHead; // 如果只有大于等于x的节点，返回原链表
else if (listLessThanX && listEqualOrGreaterThanX == NULL)
return pHead; // 如果只有小于x的节点，返回原链表
ListNode* cur1 = listLessThanX, *cur2 = listEqualOrGreaterThanX;
// 2. pHead遍历原链表，根据题意将当前元素接到cur1或cur2后，pHead以及cur1或cur2再指向新接入的元素
for (; pHead;) {
if (pHead == cur1 || pHead == cur2)
pHead = pHead->next; // 如果pHead指向的是已经处理过的节点，跳过
else {
if (pHead->val < x) {
cur1->next = pHead; // 将小于x的节点接到cur1后面
cur1 = cur1->next; // cur1指向新添加的节点
pHead = pHead->next; // 移动pHead到下一个节点
} else {
cur2->next = pHead; // 将大于等于x的节点接到cur2后面
cur2 = cur2->next; // cur2指向新添加的节点
pHead = pHead->next; // 移动pHead到下一个节点
}
}
}
cur2->next = NULL; // 确保链表的末尾指向NULL，防止出现环
cur1->next = listEqualOrGreaterThanX; // 将两个链表连接起来
return listLessThanX; // 返回小于x的链表头，即整个分区后的链表头
}
};
Python
class Partition:
def partition(self, pHead, x):
# 创建两个链表的头指针，分别用于存储小于x和大于等于x的节点
listLessThanX = pHead
listEqualOrGreaterThanX = pHead
# 1. 找到listLessThanX和listEqualOrGreaterThanX的首元素，cur1,cur2将始终分别指向前两者当前最后一个元素
while listLessThanX:
if listLessThanX.val < x:
break # 找到小于x的节点，跳出循环
listLessThanX = listLessThanX.next # 继续寻找
while listEqualOrGreaterThanX:
if listEqualOrGreaterThanX.val >= x:
break # 找到大于等于x的节点，跳出循环
listEqualOrGreaterThanX = listEqualOrGreaterThanX.next # 继续寻找
# 检查是否找到了小于x和大于等于x的节点
if not listLessThanX and listEqualOrGreaterThanX:
return pHead # 如果只有大于等于x的节点，返回原链表
elif listLessThanX and not listEqualOrGreaterThanX:
return pHead # 如果只有小于x的节点，返回原链表
cur1 = listLessThanX
cur2 = listEqualOrGreaterThanX
# 2. pHead遍历原链表，根据题意将当前元素接到cur1或cur2后，pHead以及cur1或cur2再指向新接入的元素
while pHead:
if pHead == cur1 or pHead == cur2:
pHead = pHead.next # 如果pHead指向的是已经处理过的节点，跳过
else:
if pHead.val < x:
cur1.next = pHead # 将小于x的节点接到cur1后面
cur1 = cur1.next # cur1指向新添加的节点
pHead = pHead.next # 移动pHead到下一个节点
else:
cur2.next = pHead # 将大于等于x的节点接到cur2后面
cur2 = cur2.next # cur2指向新添加的节点
pHead = pHead.next # 移动pHead到下一个节点
cur2.next = None # 确保链表的末尾指向NULL，防止出现环
cur1.next = listEqualOrGreaterThanX # 将两个链表连接起来
return listLessThanX # 返回小于x的链表头，即整个分区后的链表头
代码点评
代码点评
这段代码实现了链表的分割功能，根据给定的值 x 将链表分割成两部分：小于 x 的节点和大于等于 x 的节点。以下是对代码的点评：
- 逻辑清晰：代码逻辑清晰，通过两个指针 cur1 和 cur2 分别管理小于 x 和大于等于 x 的节点，有效地实现了链表的分割。
- 边界处理：代码在开始时处理了链表可能为空或所有节点值都小于或大于等于 x 的情况，确保了算法的健壮性。
- 指针操作：使用指针操作来移动和连接节点，这是链表操作中常见的技巧，有效地避免了额外的数据结构开销。
- 结尾处理：在分割完成后，代码正确地设置了 cur2->next 为 NULL，防止链表出现环，这是一个重要的细节处理。
- 代码可读性：虽然功能实现正确，但代码中的条件判断和循环可以进一步优化，以提高代码的可读性和简洁性。
时间复杂度分析
- 遍历链表：代码中有一个主要的循环，用于遍历链表中的每个节点，并对每个节点进行判断和移动。因此，时间复杂度为 O(n)，其中 n 是链表的长度。
空间复杂度分析
- 额外空间：代码没有使用额外的数据结构（如数组或额外的链表）来存储节点，只是使用了几个指针变量。因此，空间复杂度为 O(1)，即常数级空间复杂度。
改进建议
- 代码优化：可以考虑简化代码中的条件判断，例如通过直接比较 pHead 和 cur1 或 cur2 的值来决定是否跳过当前节点，而不是通过 pHead == cur1 || pHead == cur2 这样的判断。
- 错误处理：虽然代码已经考虑了一些边界情况，但可以进一步完善错误处理，例如处理输入链表为空的情况。
- 可读性提升：可以通过添加更多的注释和使用更清晰的变量命名来提高代码的可读性。
总体来说，这段代码是一个有效的链表分割实现，具有较好的时间和空间效率，但仍有改进空间以提高代码质量和可维护性。
我要更强
为了优化时间复杂度和空间复杂度，可以考虑使用更直接的方法来处理链表分割。基本思路是创建两个新的链表头，然后遍历原始链表，将节点根据其值与 x 的关系分别连接到两个新的链表中。最后，将这两个链表连接起来。这种方法避免了在原始链表上进行复杂的指针操作，使得代码更加简洁和直观。
以下是优化后的代码实现：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// 创建两个新的链表头
ListNode* lessHead = new ListNode(0); // 用于存储小于x的节点
ListNode* greaterEqualHead = new ListNode(0); // 用于存储大于等于x的节点
// 分别指向两个链表的当前尾节点
ListNode* lessTail = lessHead;
ListNode* greaterEqualTail = greaterEqualHead;
// 遍历原始链表
while (pHead) {
if (pHead->val < x) {
// 如果节点值小于x，将其添加到less链表
lessTail->next = pHead;
lessTail = pHead;
} else {
// 如果节点值大于等于x，将其添加到greaterEqual链表
greaterEqualTail->next = pHead;
greaterEqualTail = pHead;
}
// 移动到下一个节点
pHead = pHead->next;
}
// 将大于等于x的链表连接到小于x的链表后面
lessTail->next = greaterEqualHead->next;
// 确保greaterEqual链表的末尾指向NULL，防止出现环
greaterEqualTail->next = NULL;
// 返回less链表的头节点，即整个分割后的链表头
ListNode* result = lessHead->next;
// 清理创建的临时头节点
delete lessHead;
delete greaterEqualHead;
return result;
}
};时间复杂度分析
- 遍历链表：代码中有一个循环，用于遍历链表中的每个节点，并对每个节点进行判断和移动。因此，时间复杂度为 O(n)，其中 n 是链表的长度。
空间复杂度分析
- 额外空间：代码使用了两个额外的链表头节点和几个指针变量。链表头节点在逻辑上是必要的，因为它们帮助我们管理新创建的链表。因此，空间复杂度为 O(1)，即常数级空间复杂度。
这种优化方法保持了时间复杂度为 O(n)，同时通过避免在原始链表上进行复杂的指针操作，简化了代码逻辑，提高了代码的可读性和维护性。
哲学和编程思想
这种方法体现了几个重要的哲学和编程思想：
- 模块化思维：通过创建两个独立的链表来分别处理小于和大于等于 x 的节点，这种方法体现了模块化思维。每个链表都是一个独立的模块，负责处理特定类型的数据。这种模块化的设计使得代码更加清晰，易于理解和维护。
- 抽象与封装：代码中创建了两个新的链表头，并将原始链表的节点根据其值与 x 的关系分别添加到这两个链表中。这种做法抽象了链表分割的过程，封装了分割的细节，使得外部只需要关注分割的结果，而不需要了解分割的具体实现。
- 迭代与增量开发：代码通过迭代的方式遍历原始链表，并在每次迭代中决定节点的去向。这种迭代的方法体现了增量开发的哲学，即逐步构建解决方案，每次只处理一个问题或一个步骤。
- 避免副作用：通过创建新的链表来存储分割后的节点，而不是直接在原始链表上操作，这种方法避免了副作用。在原始链表上直接操作可能会导致不可预测的结果，而创建新的链表则确保了原始数据的完整性。
- 优化与性能：虽然这种方法在空间上稍微增加了一些开销（创建了两个新的链表头），但它简化了时间复杂度，保持了线性时间复杂度。这种权衡体现了优化与性能的思想，即在保证算法效率的同时，也考虑代码的简洁性和可读性。
- 面向对象编程：如果这段代码是在一个面向对象的编程环境中编写的，那么它还体现了面向对象编程的原则，如封装和继承。链表节点可以被视为对象，而链表的操作则可以被封装在类的方法中。
这些哲学和编程思想不仅适用于链表分割这个问题，也适用于许多其他编程问题和软件开发场景。通过理解和应用这些思想，可以提高代码的质量和开发效率。
举一反三
根据上述提到的哲学和编程思想，以下是一些技巧和示例代码，帮助你举一反三，应用到其他编程场景中：
1. 模块化思维
将复杂问题分解为更小、更易于管理的部分。例如，如果你需要实现一个功能来处理不同类型的数据，可以创建不同的函数或类来处理每种数据类型。
def process_integer(data):
# 处理整数数据的逻辑
pass
def process_string(data):
# 处理字符串数据的逻辑
pass
# 使用示例
data_list = [10, "hello", 20, "world"]
for data in data_list:
if isinstance(data, int):
process_integer(data)
elif isinstance(data, str):
process_string(data)2. 抽象与封装
创建抽象的数据结构或类来隐藏复杂性。例如，设计一个栈类，封装栈操作的细节。
class Stack:
def __init__(self):
self.items = []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def is_empty(self):
return not bool(self.items)
# 使用示例
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop()) # 输出: 23. 迭代与增量开发
逐步构建解决方案，每次只处理一个问题或一个步骤。例如，实现一个排序算法，可以先实现基本框架，然后逐步添加排序逻辑。
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
# 使用示例
data = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(data)
print(data) # 输出: [11, 12, 22, 25, 34, 64, 90]4. 避免副作用
在函数内部避免修改外部状态，确保函数的纯度。例如，设计一个函数，它接受输入并返回处理后的结果，但不修改任何外部变量。
def add_one(x):
return x + 1
# 使用示例
original_value = 5
new_value = add_one(original_value)
print(new_value) # 输出: 6
print(original_value) # 输出: 5，原始值未被修改5. 优化与性能
在设计算法时，考虑时间和空间的平衡。例如，使用哈希表来优化查找操作。
def find_element(arr, target):
seen = set()
for element in arr:
if target - element in seen:
return True
seen.add(element)
return False
# 使用示例
data = [1, 2, 3, 4, 5]
print(find_element(data, 7)) # 输出: True通过这些示例，可以看到如何将这些哲学和编程思想应用到不同的编程场景中，从而提高代码的质量和效率。
感谢阅读。
