I need to understand simple example
LinkedList list = new LinkedList();
list.add("J");
list.add("A");
list.add("V");
list.add("A");
I have simple LinkedList and need pass it to method reverse
public void reverse(LinkedList list) {
}
which will return reversed new list
and I do not need any ArraysUtils for reversing it
what is the short and practice way for having reversed output.
The same needed understand also for simple arrays.
You can use the Collections class.
Collections.reverse(list);
Your list will be reversed after that operation.
public void reverse(LinkedList list) {
//run till middle and swap start element with end element and so on
for(int i = 0, mid = list.size()/2, j = list.size() - 1; i < mid; i++, j--)
list.set(i, list.set(j, list.get(i)));//swap
}
Note: List.set(..,..) method returns the element previously at the specified position
list.set and list.get are very inefficient in LinkedList, since it needs to traverse up to half the list node by node to access each element. This implementation has time complexity of O(n ^ 2).try this.
public LinkedList<String> reverse(LinkedList list) {
LinkedList reverseList=null;
for(int i=list.size();i>0;i--)
{
reverseList.add(list.get(i))
}
return reverseList;
}
reverse method of Collections class is what you need i guess. You can change the implementation according to your need
/**
* Reverses the order of the elements in the specified list.<p>
*
* This method runs in linear time.
*
* @param list the list whose elements are to be reversed.
* @throws UnsupportedOperationException if the specified list or
* its list-iterator does not support the <tt>set</tt> operation.
*/
public static void reverse(List<?> list) {
int size = list.size();
if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {
for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)
swap(list, i, j);
} else {
ListIterator fwd = list.listIterator();
ListIterator rev = list.listIterator(size);
for (int i=0, mid=list.size()>>1; i<mid; i++) {
Object tmp = fwd.next();
fwd.set(rev.previous());
rev.set(tmp);
}
}
}
public ListNode reverseList(ListNode head) {
if(head == null) return head;
Stack<ListNode> stack = new Stack<ListNode>();
while(head != null) {
stack.push(head);
head = head.next;
}
ListNode dummy = new ListNode(0);
head = dummy;
while(!stack.isEmpty()) {
ListNode current = stack.pop();
head.next = new ListNode(current.val);
head = head.next;
}
return dummy.next;
}
This should be a fairly efficient solution that iterates through the list forward and backward at the same time, swapping each corresponding pair of elements.
public <E> void reverse(LinkedList<E> list) {
List<E> firstHalf = list.subList(0, list.size() / 2);
List<E> secondHalf = list.subList(list.size() / 2, list.size());
for (ListIterator<E> i = firstHalf.listIterator(),
j = secondHalf.listIterator(secondHalf.size()); i.hasNext(); ) {
E e1 = i.next();
E e2 = j.previous();
i.set(e2);
j.set(e1);
}
}
