algorithm - 查找链表中的乱序元素

Question

给定一个除单个元素外的非降序数字链表，找到单个错位元素。

我觉得必须有一个简单的算法来解决这个问题，但我想不出来。你不能真的只比较当前数字和最后一个数字，因为你有这样的情况 1, 2, 5, 3, 5 其中 3 会被错误地返回为不合适的元素。

这是我的代码:

Node* fix(Node* head) {
    if (!head || !head->next) return head;

    Node* curr = head;
    Node* prev = head;
    Node* wrongNode = head;
    Node* wrongPrev = head;


    while (curr) {
        if ((!curr->next && prev->val > curr->val) || //if at beginning or end, its outofplace
             (curr == head && curr->val > curr->next->val)) {
            wrongNode = curr;
            wrongPrev = prev;
            break;
        }

        if (curr->next && ((prev->val < curr->val && curr->next->val < curr->val) ||
             (prev->val > curr->val && curr->next->val > curr->val))) { // if both sides of element are either larger or smaller, it might be outofplace. Check by running through the list to see if list is in correct order if you skip the element.
            wrongNode = curr;
            wrongPrev = prev;

            Node* temp = head;
            Node* tempPrev = head;
            while (temp && tempPrev->val <= temp->val) {
                tempPrev = temp;
                if (temp->next == curr) temp = temp->next->next;
                else temp = temp->next;
            }

            if (!temp) break;
        }

        prev = curr;
        curr = curr->next;
    }

    if (wrongNode == head) head = wrongNode->next;
    else wrongPrev->next = wrongNode->next;
    curr = head, prev = head;


    while (curr && wrongNode->val > curr->val) {
        prev = curr;
        curr = curr->next;
    }

    if (curr == head)   head = wrongNode;
    else prev->next = wrongNode;
    wrongNode->next = curr;

    return head;
}

我基本上是扫描整个列表，如果我发现开头的元素大于下一个，或者末尾的元素小于前面的元素，那么这个元素一定是错位元素.

如果不是这种情况，我将搜索一个元素 k，该元素之前和之后的元素都大于 k 或小于 k。然后，我尝试查看列表是否在没有 k 的情况下按非递减顺序排列。如果是，则 k 不合适。如果没有，那一定是下一个(我想)。

然后我将 k 插入正确的位置。

有可能的输入，如

1, 0 其中 1 或 0 不合适。

1, 2, 5, 6, 4, 7 其中 4 不合适。

1, 2, 5, 3, 4 其中 5 不合适。

7, 1, 2 其中 7 不合适。

必须有更简单的方法来做到这一点。我只是没有看到它。

Answer 1

线性扫描列表，获取当前元素和上一个元素的差异。如果差异为负，则当前或上一个项目不合适。至少在您的情况下，可以通过尝试删除“当前”来检查这一点。如果移除导致负差异的元素不能修复列表，则移除之前的 must。

List : 1  2  5  6  4  7
diff =    1  3  1 -2  3
Trial: 1  2  5  6  *  7 --> correct
       1  2  5  *  4  7 --> incorrect (no need to check)

List : 7  1  2
diff :   -6  1
Trial: 7  *  2  --> incorrect
Trial: *  1  2  --> correct (no need to test)