Поиск элемента не по порядку в связанном списке

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 в нужное место.

Возможные входные данные, такие как

1, 0, где 1или 0 не к месту.

1, 2, 5, 6, 4, 7, где 4 не к месту.

1, 2, 5, 3, 4, к которому 5of place.

7, 1, 2, где 7 не к месту.

Должен быть более простой способ сделать это.Я просто не вижу этого.

Answer 1

Предположения

• Список находится в неубывающем порядке.
• Длина списка больше 2 и есть элемент at most 1не в порядке.

Я сделал попытку в java.

ОПРЕДЕЛЕНИЕ СВЯЗАННОГО СПИСКА

class ListNode{
    int data;
    ListNode next;
    ListNode(int d){
        data = d;
        next = null;
    }
}

ALGORITHM

• Перебор списка элементов.
• Теперь, если текущий элемент больше, чем следующий элемент-
  • Если существует элемент даже после следующего элемента, мы перемещаем окно сравнения на current,next,next to next.
  • Если после следующего элемента существует no element, мы перемещаем окно сравнения в prev,curr,next.

Код:

class ListNode{
    int data;
    ListNode next;
    ListNode(int d){
        data = d;
        next = null;
    }
}

public class Solution {
    public static void main(String[] args) {

        int[][] test = {
                        {1,2,5,3,5},
                        {1,2,5,1},
                        {1,2,5,2},
                        {7,1,2},
                        {1,2,5,6,4,7},
                        {1,2,3,4,5,6,7},
                        {1,2,5,3,4},
                        {1,2,5,3,5,6,7},
                        {1,2,5,3,4,4,4},
                        {2,3,2},
                        {3,3,2}
        };

        for(int i=0;i<test.length;++i){
            ListNode head = new ListNode(test[i][0]);
            ListNode temp = head;

            for(int j=1;j<test[i].length;++j){
                ListNode newNode = new ListNode(test[i][j]);
                temp.next = newNode;
                temp = newNode;
            }

            temp = findOutOfOrderElement(head);
            System.out.println(temp == null ? "No out of place element" : temp.data);  
        }        
    }

    private static ListNode findOutOfOrderElement(ListNode head){

        ListNode ptr  = head;
        ListNode prev = null;

        while(ptr != null && ptr.next != null){
            if(ptr.data > ptr.next.data){
                if(ptr.next.next == null){
                    if(prev == null) return ptr;
                    if(prev.data > ptr.next.data) return ptr.next;
                    else return ptr;
                }else{
                    if(ptr.data <= ptr.next.next.data) return ptr.next;
                    return ptr;
                }
            }

            prev = ptr;
            ptr= ptr.next;            
        }

        return null;
    }

}

ВЫХОД

3
1
5
7
4
No out of place element
5
3
5
3
2

Answer 2

Сканирование списка линейно, принимая разницу текущего и предыдущего элемента.Если разница отрицательная, то текущий или предыдущий элемент неуместен.Это можно проверить, по крайней мере, в ваших случаях путем пробного удаления «current».Если удаление элемента, вызывающего отрицательную разницу, не приводит к исправлению списка, тогда необходимо удалить предыдущее значение.

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)