how to reverse a list with O(1) space and O(n) time?

Question

I am looking for a method that reverses the same instance of a given list, with O(1) additional space and O(n) time.
this is not HW nor I am looking for some library method to do the job for me, as this is only an exercise for myself, and out of pure curiousity.

any ideas how to do it with O(1) additional space and O(n) time? (and if possible without reflection as well)?
signature is public <T> void reverse(List<T> list).

(*)assume get() to the head and tail of the list is O(1), but to the middle of it is O(n).

I came up with a recursive solution, but it is O(n) space, O(n) time

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

EDIT: I am looking for a java solution, for List<T>, only assumption on implementation is access time O(1) for head and tail, and using List<T> interface.

Solution 1

Just read one of the following. It is the thing you're talking about.

Please note that we're talking about singly 'linked' lists.

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

Plus an extra question for you:

How would you find Nth element from the tail of a linked list assuming it is singly linked and you have only head pointer with O(1) space and O(N) time?

Solution 2

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

Solution 3

You already know the length. So just use 1 temporary variable and start at index 0 and go on swapping list[0] and list[length -1], then list[1] and list[length-2], and so on. O(n) time and O(1) space for 1 temporary variable.

EDIT: Just noticed you assume O(n) for accessing the middle of the list. oh well. nevermind.

alternatively, store the next/previous pointers of the two elements you swapped to move towards the middle (assuming it's a doubly linked list). Then you get O(n) time.

Solution 4

As discussed, in the general case this is not doable, you need to assume something about the complexity of the individual operations. If you have constant-time next() and previous() for the iterators, use the solution already given. It should work for both LinkedList and ArrayList.

I thought about a solution which would work for a singly-linked list (but not for something like ArrayList), but sadly the ListIterators add method inserts the element before the cursor instead of after it, thus it is not doable with the List + ListIterator interfaces (if we can't patch the ListIterator implementation to cache the pre-insert element to allow a single previous() after add in O(1)).

Here, assuming a simple Node class with next-pointer:

/**
 * reverses a singly linked list.
 * @param first the fist node. This will be the new last node.
 * @param last the last node. This will be the new first node.
 */
void reverseList(Node first, Node last) {
   while(first != last) {
      Node temp = first;
      first = temp.next;
      temp.next = last.next;
      last.next = temp;
   }
}

In index terms, this would be something like this:

public void reverseList(List<T> list) {
    int index = list.size() -1;
    while(n > 0) {
       T element = list.remove(0);
       list.add(n, element);
       n--;
    }
}

In ListIterator terms, this would be something like this:

public void reverseList(List<T> list) {
    ListIterator<T> it = list.listIterator(list.size());
    while(it.previousIndex() > 0) { // we could count ourself here, too
       T element = list.remove(0);
       it.add(element);
       it.previous();
    }
}

Of course, usual singly linked list implementations will not have a O(1) previous implementation, thus it will not work there, as said before. (And they might throw a ConcurrentModificationException, or return erronous previousIndex.)

Solution 5

Here is a solution in Java, with O(n) time complexity (just a single pass) and O(1) space complexity (Using just two temporary variables):

    private static void reverseLinkedList() {//O(n) Time complexity, O(1) space complexity 

    //two temp pointers
    Node next = null, previous = null;

    while(head.next != null){
        next = head.next;//move next to next address
        head.next = previous;   //previous node will be the next node for head, so that head will point reverse         
        previous = head; //incrementing previous to the current node
        head = next; //incrementing head 

    }
    //at this point head points to last node and previous has the remaining reversed array
    head.next = previous;
    System.out.println("\nReversed");

}

Full code goes like:

  package com.test;

public class LinkedListReverse {
    private static Node  head;
    public static void main(String[] args) {

        for(int i = 0 ; i< 10 ; i++){
            addToLinkedList(i);
        }
        System.out.println("Added Data");

        printLinkedList();
        reverseLinkedList();
        printLinkedList();


    }



    private static void reverseLinkedList() {//O(n) Time complexity, O(1) space complexity 

        //two temp pointers
        Node next = null, previous = null;

        while(head.next != null){
            next = head.next;//move next to next address
            head.next = previous;   //previous node will be the next node for head, so that head will point reverse         
            previous = head; //incrementing previous to the current node
            head = next; //incrementing head 

        }
        //at this point head points to last node and previous has the remaining reversed array
        head.next = previous;
        System.out.println("\nReversed");

    }


    /* Logic for adding and printing linked list*/
    private static void printLinkedList() {
        System.out.println("Printing linked list");
        Node temp = head;
        while(temp.next != null){
            System.out.print(temp.value+" ");
            temp = temp.next;
        }
        System.out.print(temp.value+" ");//print the value at the last node


    }

    private static void addToLinkedList(int value){
        if(head == null){
            head = new Node(value, null);
        }else{
            Node temp = head;
            while(temp.next != null){
                temp = temp.next;
            }
            temp.next = new  Node(value, null);
        }
    }

}

//Linked List definition 
class Node{
    int value;
    Node next;
    public Node(int value, Node next){
        this.value = value;
        this.next = next;
    }
}

Program's Output:

Added Data
Printing linked list
0 1 2 3 4 5 6 7 8 9 
Reversed
Printing linked list
9 8 7 6 5 4 3 2 1 0 

Hope it helps :)

View more solutions

Comments

[ahmet alp balkan]

Plus an extra question for you: How would you find Nth element from the tail of a linked list assuming it is singly linked and you have only head pointer without O(1) space and O(N) time?

[ahmet alp balkan]

he's saying list, not the array.

[amit]

swapping with list[length-i] for i->n/2 is O(n), so this solution will make it O(n^2) time

[hammar]

@ahmet: Just do two passes over the list. First find the length, then subtract to get the index and traverse again from the start to find that index. O(2n) = O(n).

[Botz3000]

Yes, as i mentioned i just noticed you can't access it randomly in constant time. see edit.

[davin]

This would work with a doubly linked list and two pointers. O(1) space, O(n) time.

[ahmet alp balkan]

There's a faster way. In terms of complexity, yet's it is still O(n), however there's efficient way with just one pass. Try to find it (:

[amit]

@ahmet: I see some solutions assume pointers or LinkedList (I want a general implementation, for List<T>, though I didn't get to all of the links yet... will be glad for a shortcut for the one you guys discuss on comments. also: editted the question, looking for a generic solution, without assuming anything on List<T> implementation, and using only its interface.

[davin]

@ahmet, the quicker solution would be: Start with a pointer at the head of the list, traverse N elements, then add a second pointer, and traverse with both pointers (incrementing equally), until the first pointer reaches the end.

[amit]

editted the question, I am looking for java implementation for the List < T > interface.

[ratchet freak]

you got that from me, it's a near perfect copy of the code ;)

[ahmet alp balkan]

@amit I'm assuming you're using Java here (syntax looks like java). You cannot apply such algorithm without internally reaching Node structure of underlying List implementation. As you can see, all of those links implement their Node and List. geek-o-pedia.blogspot.com/2007/07/… and stackoverflow.com/questions/354875/…

[amit]

@ratchet: first I thought this is what I was looking for, but I am not sure on a second thought we can assume prviousIndex() is O(1)...:\

[ikegami]

Extra question answer: Count the number of elements in the list (O(1) or O(N) depending on implementation), then find element find element size-N from the start (O(N)).

[amit]

@ahmet: I am aware of the solution with Nodes, I was trying to see if maybe I am missing something or indeed, with just using the List interface, what I was trying to do is impossible.. your links was nice reading though. +1 for that. :)

[ikegami]

Not true. Number of ->next using ikegami's method: size-N or 2*size-N. Using davin's method: N+2*(size-N) = 2*size-N. ikegami's method is at least as good as davin's method, and much better if the list keeps track of its size. Bonus: ikegami's method should result in fewer cache misses.

[ratchet freak]

previousIndex() is too easy not to do it. but indeed previous can't be done in O(1) on singly linked lists, while there are ways of reversing a singly linked list in O(n) time and O(1) space it's pretty specific (pop from the source and push to dest) to them and array based lists will then run O(n^2) and/or O(n) memory on the same algo depending (shifting the array) or dest preallocating

[brady]

You don't need to use previousIndex(). You can keep your own counter. But, the list iterator returned from LinkedList has an O(1) implementation for previousIndex().

[brady]

@ahmet - Where do you see inconstant space requirements?

[ratchet freak]

yeah but singly linked lists have O(k) (k is current index) for previous() and java.util.LinkedList in java is double-linked

[Steve Jessop]

@amit: I think we can assume that (see my comments below the main question). Java's List interface is under-specified with respect to complexity, but if we can't assume that previous and/or previousIndex are O(1) (because it might be a singly-linked list), then we can't assume that next or nextIndex are either (because it might be a reverse singly-linked list). Reading a bit between the lines of the docs, I think List has to be doubly-, not singly-linked.

[ratchet freak]

@Steve no need to read between the lines "All of the operations perform as could be expected for a doubly-linked list."

[Steve Jessop]

@ikegami: in the bad case (where the list doesn't keep track of its size), and assuming an LRU cache, ikegami's method will result in more cache misses then davin's where N is small enough for that many nodes to fit in the cache, but the whole list is too big for the cache. Otherwise it's the same number of cache misses. In the good case (where the list knows its size in O(1)), your way is obviously superior.

[ahmet alp balkan]

Yeah, however here we don't know number of nodes and since we don't know about cache policy, we can't comment about misses.

[Steve Jessop]

@ratchet: that's for LinkedList, though, which is a concrete class. The question is about List, which is the container interface implemented by both LinkedList and ArrayList, and that insinuates certain performance characteristics but as far as I can tell doesn't come out and say them

[Steve Jessop]

@ahmet: hang on, if we can't comment about cache policy or misses, how could you say to hammar that there's a "faster" answer (presumably davin's)? It's only faster in the sense that we expect it to have a better chance of making good use of cache. ikegami's answer is identical to hammar's except that ikegami also considers the case of a list that tracks its size, in which case davin's answer is obviously suboptimal. And the hammar solution performs the same memory accesses as davin's in a different order, so the only chance for different performance is cache differences.

[ratchet freak]

@steve The List interface provides a special iterator, called a ListIterator, that allows element insertion and replacement, and bidirectional access in addition to the normal operations that the Iterator interface provides. ok nothing said about time complexity but it can be assumed O(1) for both directions

[Steve Jessop]

@ratchet: yes, that's what I originally said. In all common sense we have to assume it, but we must read between the lines to do so because the Java documentation fails to formally state it. It's those friendly technicians at Sun, trying to come across all conversational. Oracle will presumably take a more "tell you what, you try it and see whether we sue you" line ;-)

[Paŭlo Ebermann]

@davin: This is not really quicker, both variants need n-N next accesses.

[ikegami]

@ahmet alp balkan, I'm going on the assumption that many lists have nodes constructed in the other in which they appear in the list, and that memory allocations done one after another are more likely to be allocated near each other. If you buy the assumption, mine's likely to be better. If you don't buy the assumption, then nothing can be divined about cache misses, and my solution s still just as good and better than davin's.

[amit]

@ahmet, @Steve: I will appritiate if you guys can have a look at the comment I just posted (under the question) about a possible way to achieve O(1) memory and share your opinion about it.

[amit]

This seems to be O(n) space, for the stack trace of the recursive calls, while the questions asks for O(1) space.

[eivour]

If you don't know the size beforehand and if you care about cache misses, a quicker solution(in terms of next accesses) is to keep track of the last two of every N nodes, and when you reach the end come back and traverse the last at-most-2N items. Assuming "pushing the new pointer" can be done in the register and the time is negligible, it only needs at most n+N next accesses, where both davin and ikegami's solution requires 2n-N accesses.

[Eduardo Sebastian]

the idea is work with the List interface of java