//code inside a reverse method that has the list object
//passed as a parameter from main method
int size = list.size();
//create temporary list object to hold contents of original list in reverse
MyListReferenceBased temp = new MyListReferenceBased();
for (int i = 0; i < size; i++)
{
//list add method requires which index your adding to, and object
//get method just gets the object at the specified index in list
temp.add(i, list.get((size-i)-1));
//remove method just removes object at specified index
list.remove((size-i)-1);
}
//now that original list is empty, put the contents back in
for (int i = 0; i<size; i++)
{
list.add(i, temp.get(i));
}
temp.removeAll();
//end result: original list is now reversed
//and temporary array is all empty
System.out.println("List has been Reversed.");
//is there a way to get rid of the 2nd loop?? Not possible to just assign?
因此,这段代码位于主类内的反向方法中,用于反转链接列表。一般来说,反转一个列表,因为主类的用户不应该直接与链接列表交互,而只是访问链接列表方法(在链接列表类中没有进行反向操作)。相反,在主/驱动程序类中,我首先创建第二个/临时链接列表,将原始列表中的每个元素(反向)添加到新列表中,从而逆转列表。然后,由于我需要原始列表中的内容,并且只需要在此方法期间使用临时列表,所以我将元素复制回旧列表中。
在此main类的main方法中,将列表对象实例化为本地对象,然后调用反向方法,将列表对象作为参数传递。与第二个循环不同,难道没有一种方法只将临时list对象分配给原始列表吗?当我在列表的底层实现使用数组时,我能够做到这一点,但不知道如何使用链接列表。
或者其他有效率的工作?记住,这是专门用于反转链接列表,而不是直接在链接列表类中。
/全文代码(如有需要)://
public class MyListReferenceBased implements ListInterface {
private Node head;
public MyListReferenceBased()
{
head = null;
}
public boolean isEmpty() {
return head == null;
}
// dont use find()
public int size() {
int size = 0;
Node curr = head;
while (curr != null) {
curr = curr.getNext();
size++;
}
return size;
}
private Node find (int index)
{
Node curr = head;
for (int skip = 0; skip < index; skip++)
{
curr = curr.getNext();
} // end for
return curr;
} // end find
public void add(int index, Object item)
throws ListIndexOutOfBoundsException
{
if (index >= 0 && index < size() + 1)
{
if (index == 0)
{
// insert the new node containing item at
// beginning of list
Node newNode = new Node(item, head);
head = newNode;
}
else
{
Node prev = find(index-1);
Node newNode = new Node(item, prev.getNext());
prev.setNext(newNode);
} // end if
}
else
{
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on add");
} // end if
} // end add
public Object get(int index)
throws ListIndexOutOfBoundsException
{
if (index >= 0 && index < size())
{
Node curr = find(index);
Object dataItem = curr.getItem();
return dataItem;
}
else
{
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on get");
} // end if
} // end get
public void remove(int index)
throws ListIndexOutOfBoundsException
{
if (index >= 0 && index < size())
{
if (index == 0)
{
head = head.getNext();
}
else
{
Node prev = find(index-1);
Node curr = prev.getNext();
prev.setNext(curr.getNext());
} // end if
}
else
{
throw new ListIndexOutOfBoundsException(
"List index out of bounds exception on remove");
} // end if
} // end remove
public void removeAll() {
head = null;
}
public String toString() {
String x = "";
Node curr = head;
int size = size();
for (int i = 0; i < size ; i++) {
// curr.getNext();
x += curr.getItem() + " ";
curr = curr.getNext();
}
return x;
}
}
//节点类/
public class Node
{
private Object item;
private Node next;
public Node(Object newItem)
{
item = newItem;
next = null;
} // end constructor
public Node(Object newItem, Node nextNode)
{
item = newItem;
next = nextNode;
} // end constructor
public void setItem(Object newItem)
{
item = newItem;
} // end setItem
public Object getItem()
{
return item;
} // end getItem
public void setNext(Node nextNode)
{
next = nextNode;
} // end setNext
public Node getNext()
{
return next;
} // end getNext
} // end class Node
发布于 2022-10-10 03:24:56
那么,将一个又一个节点添加到一个初始空列表中:
/** Prepend the elements of <code>suffix</code> to <code>suffix</code>,
* in reverse order.
* @param emptied gets, well, <i>emptied</i>
* @param suffix
* @return <code>suffix</code> with the elements of
* <code>emptied</code> prepended in reverse order */
static ListInterface
prependReversed(ListInterface emptied, ListInterface suffix) {
while (!emptied.isEmpty()) {
suffix.add(0, emptied.get(0));
emptied.remove(0);
}
return suffix;
}
/** Reverse a List.
* @param emptied the list to reverse; will be empty on return
* @return a <code>MyListReferenceBased</code> containing
the elements of <code>emptied</code> in reverse order */
static MyListReferenceBased reverse_(ListInterface emptied) {
return prependReversed(emptied, new MyListReferenceBased());
}
/** Reverse a MyListReferenceBased in place (sort of).
* Argument is emptied temporarily and restored on return.
* @param toReverse the list to reverse; will be restored on return
* @return a <code>MyListReferenceBased</code> with
the elements of <code>toReverse</code> in reverse order */
public static MyListReferenceBased reverse(ListInterface toReverse) {
MyListReferenceBased
reversed = new MyListReferenceBased(),
saved = new MyListReferenceBased();
// an O(1) toReverse.clone() or saved.addAll(toReverse) would come in handy
while (!toReverse.isEmpty()) {
Object item = toReverse.get(0);
reversed.add(0, item);
saved.add(0, item);
toReverse.remove(0);
}
prependReversed(saved, toReverse);
return reversed;
}
真正的非变异变体(在O(1)时间…中)留作练习。
发布于 2022-10-10 04:00:00
这里是递归实现。
基本大小写:尾巴变成一个新的头,即index
参数等于size
(或者更大,如果给定的列表为空的话)。
递归案例:
0
;
get()
交换的下一个节点,即要从size - 2
开始交换的节点索引(因为删除并立即添加尾节点是多余的),并移向1
.
remove()
以删除当前节点;
1
.
reverse()
递归地传递索引,将新节点添加到尾部。
这就是它的样子:
public static void reverse(MyListReferenceBased list) {
reverse(list, 1, list.size()); // initial index is 1 (if the first call would with the index 0 the list would not change its state after the first execution of `reverse()` because we would be dialing with tail node which would stay on the same place)
}
public static void reverse(MyListReferenceBased list, int index, int size) {
if (index >= size) return; // Base case - tail becomes a head (we don't need to touch the tail)
// recursive case
Object valueToRemove = list.get(size - 1 - index);
list.remove(size - 1 - index);
list.add(size - 1, valueToRemove);
reverse(list, index + 1, size);
}
https://stackoverflow.com/questions/74013746
复制