每日一题——力扣206. 反转链表（举一反三、思想解读）

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三
题目链接

菜鸡写法编辑

代码点评

代码分析

时间复杂度

空间复杂度

专业点评

另一种方法编辑

代码点评

代码逻辑

时间复杂度

空间复杂度

专业点评

我要更强

代码点评

代码逻辑

时间复杂度

空间复杂度

点评

这种方法用到哪些哲学和编程思想

1. 迭代思想

2. 逐步构建

3. 指针操作

4. 空间效率

5. 不变性和可变性

6. 递归与迭代的对比

7. 抽象和具体化

举一反三

1. 理解数据结构的性质

2. 分步骤解决问题

3. 空间复杂度意识

4. 循环和迭代

5. 修改现有结构 vs 新建结构

6. 不变量的使用

7. 对可变性的控制

8. 边界案例和错误处理

菜鸡写法

// 定义了一个用于反转单链表的函数。接受一个指向链表头节点的指针。
struct ListNode* reverseList(struct ListNode* head) {// 如果链表为空或只有一个节点，直接返回头指针，因为无需反转。if(head==NULL||head->next==NULL)return head;// 定义三个指针用于遍历链表和反转操作。struct ListNode* tmp1=NULL;struct ListNode* tmp2=NULL;struct ListNode* newHead;// 查找链表的尾节点，将其作为新的头节点（但这个过程实际上并不改变链表结构）。for(newHead=head;newHead->next!=NULL;newHead=newHead->next) {// 空循环体，仅用于遍历到链表末尾。}// 开始反转链表的过程。for(tmp1=head,tmp2=newHead;tmp2->next!=head;) {// 查找倒数第二个节点。for(tmp1=head;tmp1->next->next!=NULL;tmp1=tmp1->next) {// 空循环体，仅用于遍历。}// 再次遍历到链表末尾的节点，这一步似乎是多余的，因为tmp2已经是最后一个节点。for(tmp2=newHead;tmp2->next!=NULL;tmp2=tmp2->next) {// 空循环体。}// 将倒数第二个节点连接到最后一个节点。tmp2->next = tmp1;// 并将倒数第二个节点的next设置为NULL，断开与前一个节点的连接。tmp1->next = NULL;}// 返回新的头节点，即原链表的尾节点。return newHead;
}

代码点评

这段代码的目标是反转一个单链表。然而，它采用了一种非常不典型且低效的方法来实现这一目标。让我们从几个方面来进行分析。

代码分析

首先，代码的基本逻辑是试图通过找到链表的最后一个节点来开始反转过程，然后逐步将每个节点移动到这个位置。这种方法虽然在逻辑上可行，但远非最优解。

时间复杂度

时间复杂度是衡量算法运行时间长短的一个指标。对于这段代码，我们注意到它包含多层嵌套循环。最外层循环的目的是为了重复反转操作，而内层的两个循环则是寻找链表的倒数第二个节点（tmp1）和最后一个节点（tmp2）。这种多层嵌套循环的使用导致了非常高的时间复杂度。

对于一个包含 n 个节点的链表，最外层循环需要执行 n 次，因为每次循环只能将一个节点移动到正确的位置。
内层循环每次都会遍历整个链表来查找倒数第二个节点，因此，它们的时间复杂度也是 O(n)。

因此，总的时间复杂度为 O(n^2)，这是因为对于每个节点，算法都需要遍历整个链表来找到它应该在反转后的位置。这种方法显然不是反转链表的最佳方案。

空间复杂度

空间复杂度衡量的是算法在执行过程中需要的额外空间。这段代码的空间复杂度相对较低，为 O(1)。这是因为无论链表的大小如何，它只需要维护几个额外的指针（tmp1、tmp2 和 newHead），这些指针的数量不随链表大小变化而变化。

专业点评

从专业角度来看，这段代码虽然能够实现链表反转的功能，但其方法过于复杂且效率低下。在实际应用中，我们通常采用更高效且更直观的算法，例如迭代法或递归法，这些方法的时间复杂度为 O(n)，空间复杂度为 O(1)（迭代法）或 O(n)（递归法，因为递归调用栈的使用）。

迭代法通过遍历链表一次，逐个调整节点的指向，就可以完成链表的反转，而无需如此复杂的多次遍历和无效操作。因此，尽管这段代码在逻辑上是正确的，它并不是解决问题的最佳方案。在编写代码时，寻找更高效的算法总是非常重要的，这不仅可以提升代码的运行速度，还可以提高代码的可读性和可维护性。

另一种方法

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/struct ListNode* reverseList(struct ListNode* head){int arr[5001]={0},i;struct ListNode* cur=head;for(i=0;cur;cur=cur->next,i++){arr[i]=cur->val;}i--;for(cur=head;cur;cur=cur->next,i--){cur->val=arr[i];}return head;
}

代码点评

这段代码提供了一种通过使用数组作为中介来反转单链表的方法。整体上，这种方法虽然相对直观，但并不是最优解。下面是对这段代码的专业点评，包括时间复杂度和空间复杂度的分析。

代码逻辑

**遍历链表并存储值：**初始遍历链表，将每个节点的值存储到一个固定大小的数组arr中。数组大小被设定为5001，这意味着代码假设链表的最大长度不会超过5000个节点。
**反向赋值：**第二次遍历链表时，按反向顺序从数组arr中读取值，并重新赋值给各个链表节点。

时间复杂度

第一次遍历链表有一个时间复杂度为O(n)，其中n是链表中的节点数量，因为它需要遍历整个链表一次。
第二次遍历同样有一个时间复杂度为O(n)，因为它再次遍历整个链表来重新赋值。
因此，总体时间复杂度为O(n) + O(n) = O(2n)，简化后为O(n)。

空间复杂度

数组arr的空间复杂度为O(m)，其中m是数组的固定大小，这里是5001。尽管这个空间用于存储链表的值，但由于其大小固定，我们可以认为这里的空间复杂度是O(1)，意味着与链表的长度无关。
没有使用递归调用或动态分配额外的数据结构，所以除了数组arr以外，没有使用额外的空间。

专业点评

假定限制：使用固定大小的数组（5001个元素）来存储链表的值是这段代码的一个主要限制。这意味着它只能正确处理最多5000个节点的链表。对于更大的链表，这段代码将无法工作。
效率和优化：虽然这种方法的时间复杂度为O(n)，与一些更直接的链表反转方法相同，但它通过增加一个额外的数组来存储链表的值，这增加了额外的空间复杂度。更优的链表反转方法（例如迭代或递归反转）可以直接在链表上操作，而无需额外的存储空间。
实用性：这段代码在实际应用中的实用性受到限制，因为它假设了链表的最大长度。在处理未知长度的链表时，更灵活的方法是直接操作链表的指针。

总的来说，这段代码为链表反转问题提供了一个有趣的解决方案，但它不是最优的。对于实际应用，推荐使用直接在链表上操作的方法，这样可以避免固定长度数组带来的限制，并且减少空间复杂度。

我要更强

struct ListNode* reverseList(struct ListNode* head) {struct ListNode* prev = NULL;struct ListNode* curr = head;while (curr) {struct ListNode* next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;
}

代码点评

这段代码是一个用来反转单链表的经典迭代方法。它通过重新指定节点间的链接关系来实现链表的反向，不需要额外的数组或数据结构来存储链表的节点值。下面是对这段代码的专业点评，包括时间复杂度和空间复杂度的分析。

代码逻辑

**初始化指针：**使用三个指针prev、current和next来跟踪链表的节点。prev初始化为NULL，因为反转后的链表的第一个节点将指向NULL。
**遍历链表：**遍历整个链表，对于每个节点，暂时保存它的下一个节点（next），然后将它的next指针指向prev节点，从而实现反转。之后，prev和current都向前移动一个节点。
**更新头指针：**遍历完成后，prev将指向原链表的最后一个节点，这时候它成了反转后的链表的头节点。更新head指针指向prev。