Понимать бесконечный цикл в алгоритме связанного списка с именем «Разделение» - PullRequest
Новая
       28

Понимать бесконечный цикл в алгоритме связанного списка с именем «Разделение»

0 голосов
/ 23 декабря 2018

Я пытаюсь решить проблему «2.4 Разделение» из книги «Взлом собеседования по кодированию»: Проблема: Учитывая связанный список и значение x, разбейте его так, чтобы все узлы, меньшие чем x, предшествовали узлам, большим илиравно х.

Каким-то образом это идет в бесконечный цикл.Решение из книги немного отличается от моего (комментируется решение книги).Я пытаюсь понять, почему решение из книги работает, а мое - нет.

public static Node particion(Node node, int x) {

    Node beforeStart = null;
    Node beforeEnd = null;
    Node afterStart = null;
    Node afterEnd = null;

    while (node != null) {

//      Node next = node.next;

//      node.next = null;

        if (node.data < x) {
            if(beforeStart == null) {
                beforeStart = node;
                beforeEnd = beforeStart;
            } else {
                beforeEnd.next = node;
                beforeEnd = node;
            }
        } else {
            if(afterStart == null) {
                afterStart = node;
                afterEnd = afterStart;
            } else {
                afterEnd.next = node;
                afterEnd = node;
            }
        }
//      node = next;

        node = node.next;
    }

    if(beforeStart == null) {
        return afterStart;
    }

    beforeEnd.next = afterStart;
    return beforeStart;
}

вход: 3 5 8 5 10 2 1 (раздел = 5) выход: 3 2 1 5 8 5 10

вместо этого мой бесконечный вывод: 3 2 1 5 85 10 2 1 5 8 5 10 2 1 5 8 5 10 2 1 5 8 5 10 (и т. Д.)

...