广西建设协会网站首页房产网站排行

题目及要求

双指针

思路：遍历链表，并在访问各节点时修改 next 引用指向，首先，检查链表是否为空或者只有一个节点，如果是的话直接返回原始的头节点，然后使用三个指针来迭代整个链表：prev（前一个节点）、curr（当前节点）和nextNode（下一个节点），在每一步迭代中，将curr的next指针指向prev，然后更新prev和curr指针为下一个节点，直到遍历完整个链表。最后返回新的头节点prev，即原链表的尾节点。这样就完成了链表的反转操作
时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
public:ListNode* reverseList(ListNode* head) {// 检查链表为空或只有一个节点的情况，直接返回原链表头节点if (!head || !head->next) {return head;}ListNode* prev = nullptr;  // 用于存储当前节点的前一个节点ListNode* curr = head;     // 当前节点指针，初始指向链表头节点while (curr) {ListNode* nextNode = curr->next;  // 保存当前节点的下一个节点curr->next = prev;                // 将当前节点的指针指向前一个节点，实现反转prev = curr;                      // 更新前一个节点为当前节点curr = nextNode;                  // 更新当前节点为下一个节点}return prev;  // 返回反转后的链表头节点}
};