如何反转具有O（1）空间和O（n）时间的列表？

algorithm list java

2022-09-03 06:18:07

我正在寻找一种方法来反转给定列表的相同实例，具有O（1）额外空间和O（n）时间。
这不是HW，也不是我正在寻找一些库方法来为我完成工作，因为这只是我自己的练习，纯粹出于好奇。

任何想法如何用O（1）额外的空间和O（n）时间来做到这一点？（如果可能的话，也没有反射）？
签名是。

（*）假设 get（）到列表的头尾是 O（1），但到它的中间是 O（n）。

我想出了一个递归解，但它是O（n）空间，O（n）时间public <T> void reverse(List<T> list)

public <T> void reverseAux(List<T> list,int size) {
    if (size == 0) return;
    T elem = list.remove(size-1);
    reverseAux(list,size-1);
    list.add(0,elem);
}
public <T> void reverse(List<T> list) {
    reverseAux(list, list.size());
}

编辑：我正在寻找一个java解决方案，因为，实现的唯一假设是头部和尾部的访问时间O（1），并使用接口。List<T>List<T>

答案 1

只需阅读以下内容之一。这就是你所说的。

请注意，我们谈论的是单一的“链接”列表。

http://www.teamten.com/lawrence/writings/reverse_a_linked_list.html

http://www.mytechinterviews.com/reverse-a-linked-list

http://www.geekpedia.com/code48_Reverse-a-linked-list.html

http://www.codeproject.com/KB/recipes/ReverseLinkedList.aspx

另外还有一个额外的问题要问你：

假设链表的尾部是第一个元素，并且你只有带有O（1）空间和O（N）时间的头指针，你如何从它找到它？N

答案 2

使用 ListIterators：

ListIterator<T> head = list.listIterator();
ListIterator<T> tail = list.listIterator(size);//assuming this can be done in O(1) though O(n) doesn't hurt that much and total is still O(n)
while(head.nextIndex()<tail.previousIndex()){
    T tmp = head.next();
    head.set(tail.previous());
    tail.set(tmp);
}