Reverse Linked List

206. 反转链表

分析

初始化指针
- 定义一个指针 prev，初始值为 nullptr，用于指向反转后链表的头节点
- 定义一个指针 cur，初始指向链表的头节点 head，用于遍历链表
遍历链表
- 在遍历的每一步，保存当前节点的下一节点 next
- 调整当前节点 cur 的 next 指针，使其指向 prev，实现反转
- 将 prev 更新为当前节点 cur，将 cur 更新为 next
终止条件
- 当 cur 遍历到链表末尾（即为 nullptr ）时，链表已经完全反转，此时 prev 指针指向反转后的链表头节点

时间复杂度

时间复杂度 O(n)，其中 n 为链表的长度。每个节点访问一次

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37


class Solution
{
public:
    ListNode* reverseList(ListNode* head)
    {
        ListNode* prev = nullptr;  // 初始化反转链表的头节点为 nullptr
        ListNode* cur = head;      // 从链表头节点开始遍历
        while (cur)                // 遍历整个链表
        {
            ListNode* next = cur->next; // 保存当前节点的下一节点
            cur->next = prev;          // 将当前节点的 next 指向反转链表的头
            prev = cur;                // 更新 prev 为当前节点
            cur = next;                // 继续遍历下一个节点
        }
        return prev;                   // 返回反转后的链表头节点
    }
};

// 递归
class Solution
{
public:
    ListNode* reverseList(ListNode* head)
    {
        // 递归终止条件：空节点或只有一个节点时直接返回
        if (!head || !head->next) return head;

        // 递归反转后面的链表，tail 是反转后的新头节点
        ListNode* tail = reverseList(head->next);

        // 将当前节点放到反转链表的尾部
        head->next->next = head;
        head->next = nullptr;

        return tail;  // 返回新的头节点
    }
};