在 LinkedList 中反转对象的问题 [英] Issues with reversing objects in a LinkedList

问题描述

我正在为一个赋值编写代码，该代码需要一个方法来反转 LinkedList 中的元素，给定要反转的列表部分.例如，如果用户输入 3，该方法将反转数组中的前 3 个元素.我已经为它编写了代码，但它没有反转代码，而是将第二个元素替换为第一个索引中存在的元素.我唯一的问题似乎是 reverseFirstSome 方法.我不是要你为我编写代码，但任何指向正确方向的指针都将不胜感激.这是我的课程的完整代码:

I'm writing code for an assignment that requires a method which reverses elements in a LinkedList, given the portion of the list to reverse. For example, if the user enters 3 the method would reverse the first 3 elements in the array. I've written code for it but instead of reversing the code it simply replaces the 2nd element with the element present in the first index. My only issue seems to be the reverseFirstSome method. I'm not asking you to write the code for me, but any pointer in the right direction would be appreciated. Here is my full code for the class:

import java.util.NoSuchElementException;

public class LinkedList
{
    //nested class to represent a node
    private class Node
    {
        public Object data;
        public Node next;
    }
//only instance variable that points to the first node.
private Node first;

// Constructs an empty linked list.
public LinkedList()
{
    first = null;
}


// Returns the first element in the linked list.
public Object getFirst()
{
    if (first == null)
    {
        NoSuchElementException ex
                = new NoSuchElementException();
        throw ex;
    }
    else
        return first.data;
}

// Removes the first element in the linked list.
public Object removeFirst()
{
    if (first == null)
    {
        NoSuchElementException ex = new NoSuchElementException();
        throw ex;
    }
    else
    {
        Object element = first.data;
        first = first.next;  //change the reference since it's removed.
        return element;
    }
}

// Adds an element to the front of the linked list.
public void addFirst(Object element)
{
    //create a new node
    Node newNode = new Node();
    newNode.data = element;
    newNode.next = first;
    //change the first reference to the new node.
    first = newNode;
}

// Returns an iterator for iterating through this list.
public ListIterator listIterator()
{
    return new LinkedListIterator();
}

public String toString() {
    LinkedListIterator iterator = new LinkedListIterator();
    String result = "{ ";
    while (iterator.hasNext())
        result += (iterator.next() + " ");
    result += "}
";
    return result;
}

public int size(){
    LinkedListIterator iterator = new LinkedListIterator();
    int a = 0;
    while (iterator.hasNext()){
        iterator.next();
        a++;
    }
    return a;
    }

public void addElement(Object obj, int index){
    if (index < 0 || index > size() ){
        IndexOutOfBoundsException ex = new IndexOutOfBoundsException();
        throw ex;
    }
    LinkedListIterator iterator = new LinkedListIterator();
    for(int i = 0; i < index; i++){
        if (iterator.hasNext()){
            iterator.next();
        }else{
            NoSuchElementException ex = new NoSuchElementException();
            throw ex;
        }
    }
    if (iterator.hasNext()){
        Object a = iterator.next();
        iterator.set(obj);
        while(iterator.hasNext()){
            Object b = iterator.next();
            iterator.set(a);
            a = b;
        }
        iterator.add(a);
    }
    else
        iterator.add(obj);
}
public Object getElement(int index)
{
    LinkedListIterator it = new LinkedListIterator();

    for(int i = 0; i < index; i++)
    {it.next();}
    return it.next();
}
public Object removeElement(int index)
{
    if(index<0)
    {NoSuchElementException ex = new NoSuchElementException();
        throw ex;}

    if(index>size()-1)
    {NoSuchElementException ex = new NoSuchElementException();
        throw ex;}

    Object result = null;

    LinkedListIterator it = new LinkedListIterator();
    result = getElement(index);
    if(index<size()-1)
    {
        for(int i = 0; i<index+1; i++)
            it.next();
        while(index<size()-2)
        {
            it.set(getElement(index+1));
            it.next();
            index++;
        }
        it.remove();
    }
    else
    {
        for(int i = 0; i<index+1; i++)
            it.next();
        it.remove();
    }

    return result;
}

public String findSmallest() {
    LinkedListIterator iterator = new LinkedListIterator();
    if (!iterator.hasNext()){
        return null;
    }
    String smallest = (String) getFirst();
    while (iterator.hasNext()) {
        if (smallest.compareToIgnoreCase((String) iterator.next()) > 1) {
            smallest = (String) iterator.next();
        }
    }
    return smallest;
}

public void searchAndReplace(Object first, Object second){
    LinkedListIterator iterator = new LinkedListIterator();
    while(iterator.hasNext()){
        if(iterator.next().equals(first)){
            iterator.set(second);
        }
    }

}
public void searchAndRemove(Object toBeRemoved){
    LinkedListIterator iterator = new LinkedListIterator();
    int a = 0;
    while(iterator.hasNext()){
        if(iterator.next().equals(toBeRemoved)){
            removeElement(a);
        }
        a++;
    }


}
public void reverseFirstSome(int howMany){
    LinkedListIterator it = new LinkedListIterator();
    if(size() > 1){
        int top = howMany - 1;
        int bot = 0;
        it.next();
        do{
            LinkedListIterator it1 = new LinkedListIterator();
            Object one = getElement(bot);
            Object two = getElement(top);
            it.set(two);
            it.next();
            for(int i = 0; i < top + 1; i++){
                it1.next();
                it1.set(one);
                bot++;
                top--;
            }
        }while(top > (size()/2) - 1);
    }

}


//nested class to define its iterator
private class LinkedListIterator implements ListIterator
{
    private Node position; //current position
    private Node previous; //it is used for remove() method

    // Constructs an iterator that points to the front
    // of the linked list.

    public LinkedListIterator()
    {
        position = null;
        previous = null;
    }

    // Tests if there is an element after the iterator position.
    public boolean hasNext()
    {
        if (position == null) //not traversed yet
        {
            if (first != null)
                return true;
            else
                return false;
        }
        else
        {
            if (position.next != null)
                return true;
            else
                return false;
        }
    }

    // Moves the iterator past the next element, and returns
    // the traversed element's data.
    public Object next()
    {
        if (!hasNext())
        {
            NoSuchElementException ex = new NoSuchElementException();
            throw ex;
        }
        else
        {
            previous = position; // Remember for remove

            if (position == null)
                position = first;
            else
                position = position.next;

            return position.data;
        }
    }

    // Adds an element after the iterator position
    // and moves the iterator past the inserted element.
    public void add(Object element)
    {
        if (position == null) //never traversed yet
        {
            addFirst(element);
            position = first;
        }
        else
        {
            //making a new node to add
            Node newNode = new Node();
            newNode.data = element;
            newNode.next = position.next;
            //change the link to insert the new node
            position.next = newNode;
            //move the position forward to the new node
            position = newNode;
        }
        //this means that we cannot call remove() right after add()
        previous = position;
    }

    // Removes the last traversed element. This method may
    // only be called after a call to the next() method.
    public void remove()
    {
        if (previous == position)  //not after next() is called
        {
            IllegalStateException ex = new IllegalStateException();
            throw ex;
        }
        else
        {
            if (position == first)
            {
                removeFirst();
            }
            else
            {
                previous.next = position.next; //removing
            }
            //stepping back
            //this also means that remove() cannot be called twice in a row.
            position = previous;
        }
    }

    // Sets the last traversed element to a different value.
    public void set(Object element)
    {
        if (position == null)
        {
            NoSuchElementException ex = new NoSuchElementException();
            throw ex;
        }
        else
            position.data = element;
    }
} //end of LinkedListIterator class

}//LinkedList 类结束

} //end of LinkedList class

推荐答案

我可以想到一个附加到反转列表的标准逻辑的实现.
如果传递的索引大于列表中的元素数，则它只会反转整个列表.
如果传递 0 或 1，则列表不受影响.

I can think of an implementation of appending to standard logic of reversing a list.
If you pass index greater than the number of elements in the list, then it simply reverses the entire list.
If you pass 0 or 1, the list will be unaffected.

public boolean reverseTillIndex(int index) {
    int count = 0;
    if (index == 0) {
        return false;
    }
    Node endCountNode = head;

    while (count++ < index && endCountNode != null) {
        endCountNode = endCountNode.next;
    }
    count = 0;

    // standard reverse a list code
    Node current = head;
    Node h2 = null;

    while (current != null && count++ < index) {
        head = current.next;
        current.next = h2;
        h2 = current;
        current = head;
    }

    head = h2;
    while (h2.next != null) {
        h2 = h2.next;
    }
    h2.next = endCountNode;
    return true;
}

这篇关于在 LinkedList 中反转对象的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！