链表奇偶位置重排代码出现Output Limit Exceeded问题求助

错误根源 #

你的代码触发Output Limit Exceeded是因为链表形成了循环引用，导致输出时无限打印节点数据。

具体来说，在拼接奇数链和偶数链后，你没有将偶数链的尾节点evenEnd的next置为NULL。以输入1 2 3 4 5 6 7为例：

• 处理后奇数链是1->3->5->7，偶数链是2->4->6
• 原链表中6的next原本指向7，你没有修改这个指针
• 最后将oddEnd（即7）的next指向evenSt（即2），就形成了2->4->6->7->2的循环
• 输出时遍历链表会陷入无限循环，导致输出内容超限

修复后的代码 #

只需要在拼接奇偶链之前，添加一行evenEnd->next = NULL;，切断偶数链尾节点的旧引用：

class Solution
{
    public:
    void rearrangeEvenOdd(Node *head)
    {
       if(head==NULL || head->next==NULL || head->next->next==NULL){
           return;
       }
       Node* temp = head;
       Node* oddSt = temp;
       Node* oddEnd = temp;
       temp = temp->next;
       Node* evenSt = temp;
       Node* evenEnd = temp;
        temp = temp->next;
         int n = 1;
        
       while(temp!=NULL){
           if(n%2!=0){
            oddEnd->next = temp;
            oddEnd = oddEnd->next;
           }
           else{
            evenEnd->next = temp; 
            evenEnd = evenEnd->next;
           }
          temp = temp->next; 
          n++;
       }
       
       evenEnd->next = NULL; // 新增这一行，切断循环引用
       oddEnd->next = evenSt;
    }
};

额外优化点 #

你代码中用n来判断奇偶位置的逻辑可以简化，因为从temp开始的节点本来就是第3个节点（奇数位置），之后交替奇偶，所以不需要计数，直接交替添加到奇偶链即可：

class Solution
{
    public:
    void rearrangeEvenOdd(Node *head)
    {
       if(head == NULL || head->next == NULL) return;
       
       Node* oddEnd = head;
       Node* evenSt = head->next;
       Node* evenEnd = evenSt;
       
       while(evenEnd != NULL && evenEnd->next != NULL){
           oddEnd->next = evenEnd->next;
           oddEnd = oddEnd->next;
           evenEnd->next = oddEnd->next;
           evenEnd = evenEnd->next;
       }
       
       oddEnd->next = evenSt;
    }
};

这个版本逻辑更清晰，时间复杂度还是O(N)，空间复杂度O(1)，完全符合题目要求。

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