如何查找并修正非递减链表中唯一的错位元素？

嘿，我懂你想要一个更清爽的实现——你的思路方向是对的，但我们可以利用链表原本非递减且仅存在一个错位元素这个核心条件，把代码简化很多，不需要嵌套验证循环，效率也更高！

核心思路梳理 #

因为原本是严格的非递减链表，只出了一个错位元素，所以整个链表只会出现最多一处「逆序对」（也就是前一个节点值大于当前节点值的情况）。我们只需要定位这个逆序对，就能快速确定错位元素，然后把它移到正确位置：

1. 遍历链表，找到第一个prev.val > curr.val的逆序对位置
2. 判断错位元素是prev还是curr：
   • 如果curr是尾节点，或者prev的前一个节点（如果存在）的值 ≤ curr.val，说明错位的是prev（比如1,2,5,3,4里的5，因为5>3，且前面的2≤3）
   • 否则错位的是curr（比如1,2,6,4,7里的4，因为6>4，且前面的5>4）
3. 把错位元素从原位置移除，再遍历找到它应该插入的位置（第一个大于它的节点之前），完成插入

简洁实现代码 #

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

Node* fix(Node* head) {
    // 空链表或单节点直接返回
    if (!head || !head->next) return head;

    Node *prevPrev = nullptr, *prev = nullptr, *curr = head;
    Node *wrongNode = nullptr, *wrongPrev = nullptr;

    // 找到第一个逆序对，同时记录节点前驱
    while (curr->next && curr->val <= curr->next->val) {
        prevPrev = prev;
        prev = curr;
        curr = curr->next;
    }

    // 确定错位节点和它的前驱
    if (!curr->next) {
        // 逆序对在最后两个节点，错位的是curr（比如1,0）
        wrongNode = curr;
        wrongPrev = prev;
    } else if (!prev) {
        // 逆序对在头两个节点，错位的是head（比如7,1,2）
        wrongNode = head;
        wrongPrev = nullptr;
    } else if (prev->val <= curr->next->val) {
        // prev的前一个值 <= curr->next，错位的是curr（比如1,2,6,4,7）
        wrongNode = curr;
        wrongPrev = prev;
    } else {
        // 错位的是prev（比如1,2,5,3,4）
        wrongNode = prev;
        wrongPrev = prevPrev;
    }

    // 移除错位节点
    if (!wrongPrev) {
        head = wrongNode->next;
    } else {
        wrongPrev->next = wrongNode->next;
    }

    // 找到插入位置
    Node* insertPrev = nullptr;
    Node* insertCurr = head;
    while (insertCurr && insertCurr->val <= wrongNode->val) {
        insertPrev = insertCurr;
        insertCurr = insertCurr->next;
    }

    // 插入错位节点
    if (!insertPrev) {
        wrongNode->next = head;
        head = wrongNode;
    } else {
        wrongNode->next = insertCurr;
        insertPrev->next = wrongNode;
    }

    return head;
}

测试用例验证 #

• 输入1,0：找到逆序对1>0，curr是尾节点，移除0后插入到1前面，得到0,1
• 输入1,2,5,6,4,7：找到逆序对6>4，判定错位节点是4，移除后插入到5前面，得到1,2,4,5,6,7
• 输入1,2,5,3,4：找到逆序对5>3，判定错位节点是5，移除后插入到末尾，得到1,2,3,4,5
• 输入7,1,2：逆序对在头两个，移除7后插入到2后面，得到1,2,7

这个解法全程只需要最多两次线性遍历，时间复杂度O(n)，空间复杂度O(1)，代码逻辑也更清晰，比嵌套循环的实现简洁多了～

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