在LinkedList中反转对象的问题
我正在为一个赋值编写代码，该赋值需要一个方法来反转LinkedList中的元素，给定列表的一部分要反转。 例如，如果用户输入3，则该方法将反转数组中的前3个元素。 我已经为它编写了代码，但它没有反转代码，而只是将第二个元素替换为第一个索引中存在的元素。 我唯一的问题似乎是reverseFirstSome方法。 我不是要求你为我编写代码，但任何正确方向的指针都会受到赞赏。 这是我的全部代码：
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 += "}\n"; 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 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(indexsize()-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 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 (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类的结尾
我可以想到一个附加反转列表的标准逻辑的实现。
如果传递的索引大于列表中的元素数，则它只是反转整个列表。
如果传递0或1，列表将不受影响。
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类中的reverseSomeMethod()的实现，我认为这在逻辑上是正确的。 它使用递归来反转列表的顺序。 在基本情况下，它将新头部分配给当前尾部，并在每个步骤中以相反方向链接列表。
public void reverseSomeMethod (Node node) { if (node == null || node.next == null) { return; } reverseSomeMethodHelper(node); // assign the new tail (the previous head) of the list to point to NULL node.next = null; } private void reverseSomeMethodHelper(Node node) { // base case: assign the new HEAD to old tail, link in reverse, and return if (node.next.next == null) { setFirst(node.next); node.next.next = node; return; } // otherwise traverse deeper in the list reverseSomeMethodHelper(node.next); // link in reverse order and return node.next.next = node; }
请注意，您可能必须调整我的代码才能使用当前的实现。 例如，我没有做太多的getter和setter，因为你原来的代码没有它们。