C/C++---------------LeetCode第LCR. 024.反转链表

题目及要求

双指针

思路：遍历链表，并在访问各节点时修改 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;  // 返回反转后的链表头节点
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22