java - 使用 swap 方法反转泛型 LinkedList

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

使用 swap 方法反转通用 LinkedList 的最佳方法是什么？ 反向方法之前:

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

在 reverse() 方法之后:

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

Answer 1

您需要做的是将列表分成两半。如果列表大小是奇数，则中间的那个将保留在原位。然后像时尚一样在镜子中交换两侧的元素。这应该比 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;
}

这是一点点伪java。当它应该立即返回时，它仍然缺少对 size = 0 或 size = 1 的检查。一个 for 循环。时间复杂度 O(n)。还有就是需要检查什么时候size = 2，直接调用swap(...)。