顛倒鏈表中的對象的問題

Question

我正在編寫一個賦值的代碼，該賦值需要一個方法來顛倒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 < 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類

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

請注意，您可能需要調整我的代碼以使用您當前的實現。例如，我沒有太多的getter和setter，因爲你的原始代碼沒有他們。