Обратный LinkList при сохранении оригинальных узлов - PullRequest
Новая
       30

Обратный LinkList при сохранении оригинальных узлов

0 голосов
/ 08 октября 2018

Мой учитель назначил программу, в которой я должен создать связанный список некоторых случайных чисел.Я должен создать его из списка, а затем вторая часть задания - отменить его.Фактическая цитата:

Напишите Java-метод reverseLinkedList (), который сгенерирует обратный связанный список из связанного списка, который вы создадите в задаче 1. Ваш метод должен принять связанный список каквход и возврат другого связанного списка, который имеет ссылки на узлы в обратном порядке.Пожалуйста, не печатайте оригинальный список в обратном порядке.Идея состоит в том, чтобы манипулировать ссылками на узлы, чтобы узлы сохранялись в том же порядке, в котором они были созданы.

Код, который я сгенерировал до сих пор, выглядит как 

import java.util.*;

public class progassignment2 
{ 
    public static void main(String args[]) 
    { 
        List<Integer> myList = new ArrayList<Integer>();
        Random ran = new Random();
        int ranNum;
        for(int x = 0;x<5;x++)
        {
            ranNum =  ran.nextInt(500);
            myList.add(x,ranNum);
        }
        LinkedList<Integer> mylinklist = createLinkedList(myList);
        System.out.println(mylinklist);
        LinkedList<Integer> mylinklistrev = reverseLinkedList(mylinklist);
    } 

    public static LinkedList createLinkedList(List<Integer> integerList)
    {
        LinkedList<Integer> linkedlist = new LinkedList<Integer>();
        linkedlist.addAll(integerList);
        return linkedlist;
    }

    public static LinkedList reverseLinkedList(LinkedList inputList)
    {
        for(int y = 0;y < inputList.size();y++)
        {
            inputList.addLast(inputList.pollFirst());
        }
        return inputList;
    }
 }

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

Ответы [ 3 ]

0 голосов
/ 08 октября 2018

Обычно упражнения в связанных списках не используют какой-либо встроенной коллекции Java (например, ArrayList, LinkedList и т. Д.), А вместо этого предназначены для создания собственного типа коллекции.

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

class Node {
    private int value;
    private Node next;

    public Node(int value){
        this.value = value;
    }

    public int getValue(){
        return value;
    }

    public Node getNext(){
        return next;
    }

    public void setNext(Node next){
        this.next = next;
    }
}

Каждый элемент указывает на следующий, и конец списка помечается следующим элементом последнего узла: null.

При использовании подобных объектоввы сможете определить свой собственный связанный список, не используя предопределенную коллекцию, предлагаемую Java.

Вы наверняка слышали о структуре данных stack: прочитав все элементы в вашемсвязать список и поместить его в стек, как только список будет закончен, вы будете собирать элементы внутри стека;создание связанного списка в порядке элементов, извлеченных из стека, решит проблему инвертирования связанного списка.

0 голосов
/ 08 октября 2018

Идея состоит в том, чтобы манипулировать ссылками на узлы, чтобы узлы сохранялись в том же порядке, в котором они были созданы.

Вам следует создать свой собственный LinkedList.Вам не разрешено использовать обычные способы реверсирования, такие как рекурсия, стек, модификации или любые методы интерфейса коллекций.

Вот ссылка включает LinkedList пути реверсирования и решение: 

class LinkedList {
    Node head; // head of list
    /* Linked list Node */

    class Node {
        int data;
        Node next;

        Node(int d) {
            data = d;
            next = null;
        }
    }

    /* Function to print reverse of linked list */
    void printReverse(Node head) {
        if (head == null)
            return;
        // print list of head node
        printReverse(head.next);

        // After everything else is printed
        System.out.print(head.data + " ");
    }

    /* Inserts a new Node at front of the list. */
    public void push(int new_data) {
        Node new_node = new Node(new_data);

        new_node.next = head;

        head = new_node;
    }

    public static void main(String args[]) {
        LinkedList llist = new LinkedList();
        llist.push(4);
        llist.push(3);
        llist.push(2);
        llist.push(1);

        llist.printReverse(llist.head);
    }
}
0 голосов
/ 08 октября 2018

А как же: 

public static LinkedList reverseLinkedList(List<Integer> inputList) {
    LinkedList<Integer> reversedLinkedlist = new LinkedList<Integer>(inputList);
    Collections.reverse(reversedLinkedlist);
    return reversedLinkedlist;
}
...