Reverse generic LinkedList by using swap method

Question

        public class SimpleLinkedList<E> {

            public Node<E> head;

            public int size;

            public void add(E e) {
                ++this.size;
                if (null == head) {
                    this.head = new Node();
                    head.val = e;
                } else {
                    Node<E> newNode = new Node();
                    newNode.val = e;
                    newNode.next = head;
                    this.head = newNode;
                }
            }

public void swap(E val1, E val2) {
        if (val1.equals(val2)) {
            return;
        }
        Node prevX = null, curr1 = head;
        while (curr1 != null && !curr1.val.equals(val1)) {
            prevX = curr1;
            curr1 = curr1.next;
        }
        Node prevY = null, curr2 = head;
        while (curr2 != null && !curr2.val.equals(val2)) {
            prevY = curr2;
            curr2 = curr2.next;
        }
        if (curr1 == null || curr2 == null) {
            return;
        }
        if (prevX == null) {
            head = curr2;
        } else {
            prevX.next = curr2;
        }
        if (prevY == null) {
            head = curr1;
        } else {
            prevY.next = curr1;
        }
        Node temp = curr1.next;
        curr1.next = curr2.next;
        curr2.next = temp;
    }

       public void reverse() {
            Node<E> prev = null;
            Node<E> current = head;
            Node<E> next = null;
            while (current != null) {
                next = current.next;
                current.next = prev;
                prev = current;
                current = next;
            }
            head = prev;
        }


        public static class Node<E> {
            public Node<E> next;
            public E val;
        }
    }


    public class SimpleLinkedListTest {

      @Test
    public void testReverseMethod() {
        SimpleLinkedList<Integer> myList = new SimpleLinkedList<>();
        for (int i = 0; i < 10; i++) {
            myList.add(i);
        }
        SimpleLinkedList<Integer> expectedList = new SimpleLinkedList<>();
        for (int i = 9; i > -1; i--) {
            expectedList.add(i);
        }
        myList.reverse();
        assertTrue(AssertCustom.assertSLLEquals(expectedList, myList));
    }
  }

What would be the most optimal way to reverse generic LinkedList by using the swap method? before reverse method :

(head=[9])->[8]->[7]->[6]->[5]->[4]->[3]->[2]->[1]->[0]-> null

after reverse() method :

(head=[0])->[1]->[2]->[3]->[4]->[5]->[6]->[7]->[8]->[9]-> null

I'm more interesting in java 7 (and below) solutions, however, I would be great to see java 8 solution as well. — , Jan 10 '17 at 15:56
reverse() method doesn't use swap(E val1, E val2) method. I need to rewrite reverse() method in a way that it utilizes swap(E val1, E val2) method. So my question is how should I rewrite reverse() method in an optimal way. — , Jan 10 '17 at 16:10
reversing a list using the provided `swap`-method is inefficient. It is possible, but you'll have to get the values you want to swap, before swapping them! So you'll have `O(n ^ 2)`, which is horrible for a reverse-method. And this sort of comparison `curr1.val != val1` for Objects is a [bad idea in java](http://stackoverflow.com/questions/7520432/what-is-the-difference-between-vs-equals-in-java#7520464). — , Jan 10 '17 at 16:33
I end up with 0(n^2) too. That's why I decided to post this question hoping that my conclusion is mistake and there is a better way. Unfortunately, my restriction is that I don't allow to change swap method and should use it. Because whatever greater cause... — , Jan 10 '17 at 16:49
Are you sure that this is the swap method that was provided? Because otherwise you could get a O(n) reversal by using swap to swap each node's `next` and `prev`. Just need to be careful then with the order of going through the list, and what happens to `head`. — cadolphs, Jan 10 '17 at 18:42
I'm also concerned that your swap method doesn't operate on nodes but on values, and then finds the first nodes where these values are. I don't think that that's correct. — cadolphs, Jan 10 '17 at 18:45

bichito · Accepted Answer · 2017-01-11T19:19:43.033

What you need to do is divide the list in half. If the list size is odd the one in the middle will remain in place. Then swap elements on either side in a mirror like fashion. This should be more efficient than O(n^2)

reverse(){
    Node current = this.head;
    int half = this.size/2;
    int midElement = this.size % 2 == 0 ? 0: half + 1;
    Stack<Node<E>> stack = new Stack<Node<E>>();

    for(int i = 0; i < this.size; i++){
        if (i < = half)
            stack.push(current);
        else{
            if (i == midElement)
                continue;
            else
                swap(stack.pop(), current);
        current = current.next;
    }
}

swap(Node<E> v, Node<E> v1){
    E tmp = v.value;
    v.value = v1.value;
    v1.value = tmp;
}

This is a little bit of pseudo java. It is missing still the checks for size = 0 or size = 1 when it should return immediately. One for loop. Time Complexity O(n). There is also the need to check when size = 2, swap(...) is to be invoked directly.

score 0 · Answer 2 · answered Jan 12 '17 at 13:53

Based on the @efekctive 's idea, there a solution. The complexity is a little bit worse than O^2 but no need changes in the swap method, no need in usage of another collection. The code below passes the unit test, however, be careful to use it there could be a bug related to size/2 operation. Hope this help.

 public void reverse() {
            Node<E> current = head;
            SimpleLinkedList<E> firstHalf = new SimpleLinkedList<>();
            SimpleLinkedList<E> secondHalf = new SimpleLinkedList<>();
            for (int i = 0; i < size; i++) {
                if (i >= size / 2) {
                    firstHalf.add(current.val);
                } else {
                    secondHalf.add(current.val);
                }
                current = current.next;
            }
            SimpleLinkedList<E> secondHalfReverse = new SimpleLinkedList<>();
            for (int i = 0; i < secondHalf.size(); i++) {
                secondHalfReverse.add(secondHalf.get(i));
            }
            for (int i = 0; i < size / 2; i++) {
                if (secondHalfReverse.get(i) == firstHalf.get(i)) {
                    break;
                }
                swap(secondHalfReverse.get(i), firstHalf.get(i));
            }
        }

Reverse generic LinkedList by using swap method

2 Answers2