Извлечение первых n элементов из односвязного списка - PullRequest
Новая
       13

Извлечение первых n элементов из односвязного списка

0 голосов
/ 04 апреля 2019

Я пытаюсь написать метод, который принимает целое число n и возвращает новый список, содержащий первые n элементов его текущего объекта List, в том же порядке, в котором они появляются в текущем списке.

Решение, которое у меня есть, представлено ниже: 

public List firstNelements(int n) {
    List newList = newList();
    Node travel = head, last = null, newNode;
    int counter = 0;
    while (counter < n && travel != null) {
        newNode = new Node();
        newNode.data = travel.data;

        if (last == null)
            last = newList.head = newNode;
        else last = last.next = newNode;

        counter++;
        travel = travel.next;
    }
    return newList;
}

Я понимаю, что метод начинается с объявления нового списка. Оттуда он объявляет узел «путешествия», который используется для итерации по всему текущему списку. Кроме того, я считаю, что «последний» как раз и предназначен для отслеживания последнего узла в текущем объекте.

Я также понимаю первую часть цикла while; Однако я не понимаю, почему условный 

if (last == null)
            last = newList.head = newNode;
        else last = last.next = newNode;

присутствует. Узел "last" является нулевым при первом выполнении кода, поэтому на первой итерации я предполагаю, что мы устанавливаем newNode в заголовок нового списка. Но почему мы обновляем последнюю версию? Означает ли это, что «last» отслеживает последний узел в новом списке? Я также понятия не имею, что здесь делает «else».

Я проследил через список {1, 2, 3} с n = 2. Однако я все еще не могу понять этого. Остальная часть цикла while (после этого условия) имеет для меня смысл.

Ответы [ 2 ]

1 голос
/ 04 апреля 2019

Объект, с которым вам нужно работать, кажется связанным списком, то есть каждый node имеет ссылку на следующий node в списке. Один узел особенный и называется head. Это позволяет перебирать все элементы от начала head до конца (когда .next равно null). Во время первой итерации это head должно быть настроено так, чтобы в списке было что-то, что будет повторяться позже. Когда last равно null, цикл while выполняется в первый раз. Если это не первый цикл, то устанавливается только указатель .next узла last, рассмотренный в предыдущем цикле, для правильного связывания между элементами.

Это домашняя работа? Возможно, Java LinkedList делает что-то подобное внутри. Если это не домашнее задание, лучшим подходом будет использование существующих решений из инфраструктуры Java Collection и, например, метод subList.

1 голос
/ 04 апреля 2019 
if (last == null) {
    last = newList.head = newNode;
} else {
    last = last.next = newNode;
}

  • Если последний равен нулю, установите newList.head на newNode, а затем last на newNode.

  • Если последнийне ноль, установите last.next в newNode и затем last в newNode.

Каждая итерация создает newNode = new Node() и присваивает newNode.data travel.data.

Допустим, итерация 1 создает Node1, а итерация 2 создает Node2.

В возвращенной структуре Node1.next должен быть Node2.

Когда мы находимся в итерации 2,Мы уже обработали Node1, не зная, что будет дальше (т.е. Node1.next равен нулю).Итак - как Node1 узнает, что «Node1.next» должен быть «Node2»?

Вот что делает это условие.

...