LeetCode 206：反转链表

LeetCode 206：反转链表

题目描述

给定单链表的头节点 head，要求反转原链表并返回反转后的链表的头指针。 要求时间复杂度为 O(n)，空间复杂度为 O(1)。

解题思路

思路一：反转指针指向

思路：遍历一遍链表，将当前结点的 next 指针，指向前驱节点，即可实现链表的反转。最终返回原链表的最后一个节点（新链表的头结点）。

操作：

1. 若 head == nullptr，直接返回 nullptr。
2. 定义 curNode 从头结点开始遍历，curPrev 记录前驱节点（初始 nullptr），curNext 保存后继结点。
3. 在循环中：
   • 保存 curNode->next 到 curNext。
   • 修改 curNode->next = curPrev。
   • 移动指针：curPrev = curNode, curNode = curNext。
4. 循环结束后返回 curPrev。

思路二：头插法

思路：创建一个新链表，头结点为 newHead（初始 nullptr）。遍历原链表，将原链表中的节点依次头插到新链表中，更新 newHead，最终返回 newHead。

操作：

1. 定义 newHead 为新链表头，curNode 遍历原链表。
2. 在循环中：
   • 保存 curNode->next 到 curNext。
   • 执行头插：curNode->next = newHead。
   • 更新新链表头：newHead = curNode。
   • 移动 curNode = curNext。
3. 返回 newHead。

代码实现

思路一：反转指针指向

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* curNode = head;
        ListNode* curPrev = nullptr;
        while (curNode) {
            ListNode* curNext = curNode->next;
            curNode->next = curPrev;
            curPrev = curNode;
            curNode = curNext;
        }
        return curPrev;
    }
};