反转链表：双指针迭代与头插法详解

优化点

无需单独判断链表为空的情况。如果 head 为空，curNode 初始即为 nullptr，循环不执行，直接返回 curPrev（即 nullptr），代码更加简洁。

方法二：头插法构建新链表

另一种思路是创建一个新链表，遍历原链表，将原链表的节点依次'头插'到新链表中。头插后更新新链表的头指针 newHead。

核心逻辑

1. 初始化：newHead 初始为 nullptr，curNode 指向原链表头。
2. 遍历与插入：
   • 同样需要先保存 curNext，因为头插操作会修改 curNode->next。
   • 将 curNode->next 指向当前的 newHead。
   • 更新 newHead 为 curNode。
   • curNode 移动到 curNext。
3. 返回结果：循环结束后，newHead 即为反转后的链表头。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* newHead = nullptr;
        ListNode* curNode = head;
        
        while (curNode) {
            // 保存后继节点
            ListNode* curNext = curNode->next;
            
            // 头插操作
            curNode->next = newHead;
            newHead = curNode;
            
            // 移动当前节点
            curNode = curNext;
        }
        
        return newHead;
    }
};

常见误区：忘记保存后继节点

在尝试头插法时，初学者容易忽略保存 curNext。如果直接在头插后通过 curNode = curNode->next 移动，由于 curNode->next 已经被修改为新链表的头，会导致无法访问原链表的剩余部分，甚至造成内存泄漏或死循环。

错误示例：

// 错误示范
while (curNode) {
    if (newHead == nullptr) {
        newHead = curNode;
        newHead->next = nullptr;
    } else {
        curNode->next = newHead;
        newHead = curNode;
    }
    // 这里 curNode->next 已经被修改，无法获取原链表下一个节点
    curNode = curNode->next; 
}

修正方法很简单，就是在修改指针前，务必先把 curNode->next 的值存到一个临时变量中。

总结

这两种方法本质上是相通的，都是利用指针操作改变链表方向。原地反转法更节省空间（虽然两者都是 O(1)），且逻辑上更符合'就地修改'的直觉；头插法则更容易理解'构建新结构'的过程。在实际面试中，推荐优先掌握原地反转法，因为它能体现对指针操作的熟练度。