LeetCode92反转链表II C++代码输出与预期不符问题咨询

我在Stack Overflow浏览时遇到了编号#92的算法题：

即Reverse a linked list 2（反转链表II），题目描述为：给定单链表的头节点和两个整数left、right，满足left <= right，要求反转链表从位置left到位置right的所有节点，返回反转后的链表。我最初理解示例输入为链表[1,2,3,4,5]、left=1、right=4时，输出应为[4,2,3,1,5]。

编写的C++代码大部分测试用例都能运行通过，但有一个测试用例的结果不符合预期：输入链表[1,2,3,4]，left=1、right=4时，代码输出为[4,2,3,1]，但题目给出的正确答案是[4,3,2,1]，始终无法理解问题所在。
实现代码如下：

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) 
    {
        int x = 1;

        ListNode * left_node = nullptr;
        ListNode * right_node = nullptr;
        ListNode * curr = head;
        int temp = 0;
                
        if (!head)
            return nullptr;
        
        while(curr)
        {
            if(x == left)
                left_node = curr;
                
            if(x == right)
                right_node = curr;
            curr = curr->next;
            ++x;
        }
        
        temp = left_node->val;
        left_node->val = right_node->val;
        right_node->val = temp;
     
        return head;
    }

问题核心原因 #

• 首先你对题目的理解存在根本性偏差：区间反转是把left到right范围内的所有节点顺序完全倒置，不是只交换区间首尾两个节点的位置。你之前认为输入[1,2,3,4,5]、left=1、right=4时输出[4,2,3,1,5]是完全错误的，这个case的正确输出是[4,3,2,1,5]。
• 你的代码逻辑只做了一件事：找到left和right位置对应的节点，交换这两个节点存储的值，区间内夹在中间的所有节点完全没有被处理。
• 之前能通过部分测试用例纯属巧合：当区间长度为1（left=right）时，交换节点自身的值不会出错；当区间长度为2（right-left=1）时，交换首尾两个节点刚好等价于反转整个区间，结果看起来正确。一旦区间长度大于等于3，中间节点顺序保持原样，输出结果必然不符合要求。

修正方案 #

要正确实现区间反转，常见有两种实现思路：

1. 值拷贝法：遍历链表把left到right区间内的节点值按顺序存入临时数组，倒序遍历数组把值重新写回对应区间的节点，实现逻辑简单不需要修改链表指针，但需要占用O(n)的额外空间。
2. 穿针引线法（面试标准解法，O(1)额外空间）：借助虚拟头节点统一处理头节点变更的边界情况，先定位到left位置的前驱节点作为锚点，遍历区间内的节点，逐个将节点插入到锚点之后，一次遍历即可完成区间反转，不需要额外存储。

穿针引线法的参考实现如下：

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        // 空链表或者区间只有一个节点直接返回
        if (!head || left == right) return head;
        // 虚拟头节点，统一处理left=1时头节点变更的场景
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* pre = dummy;
        // 移动到left位置的前一个节点
        for (int i = 0; i < left - 1; ++i) {
            pre = pre->next;
        }
        ListNode* curr = pre->next;
        // 逐次把curr后面的节点插入到pre的下一位
        for (int i = 0; i < right - left; ++i) {
            ListNode* next_node = curr->next;
            curr->next = next_node->next;
            next_node->next = pre->next;
            pre->next = next_node;
        }
        return dummy->next;
    }
};

内容的提问来源于stack exchange，提问作者Ahmad Safa