LinkedList内のオブジェクトを反転する際の問題

Question

リストの一部が逆転している場合、LinkedList内の要素を逆にするメソッドを必要とする代入のコードを記述しています。たとえば、ユーザーが3を入力した場合、メソッドは配列の最初の3つの要素を逆にします。私はそれのためのコードを書いたが、コードを逆転させるのではなく、単に第2の要素を第1のインデックスにある要素に置き換えるだけである。私の唯一の問題は、reverseFirstSomeメソッドのようです。私はあなたに私のためのコードを書くことを求めていませんが、正しい方向の任意のポインタが高く評価されます。ここでは、クラスのための私の完全なコードは次のとおりです。LinkedListのクラスの

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 < 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 

} //最後

Answer 1

私は、リストを逆転させる標準的なロジックを追加する実装を考えることができます。
リスト内の要素の数よりも大きなインデックスを渡すと、リスト全体が逆転します。
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; 
} 

Answer 2

ここで私は論理的に正しいと信じているあなたの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; 
} 

現在の実装を使用するには、コードを調整する必要があります。たとえば、元のコードにはゲッターやセッターがなかったので、私はゲッターとセッターをあまり使っていませんでした。