java - 使用假列表类

Question

我正在做一些家庭作业，我被一对夫妇难住了。我很难理解交换列表中数据的最佳方法。

我应该使方法 reverse() 并且它使用 LinkedIntList 类(如下)。这是一个有限的列表类，所以我只能使用那里的东西。

重点是取一个项目列表

[1, 2, 3, 4, 5] 并扭转他们 [5, 4, 3, 2, 1]

我以为我的伪代码是

获取第一条数据并将其附加到列表中。 遍历原始大小(因为它改变了) 并取出 0 处的那 block 然后将当前棋子添加到末尾后的 0、1 位置。

对于这样的输入: [1, 8, 19, 4, 17]
预期是这样的: 前面 -> [17] -> [4] -> [19] -> [8] -> [1]/
我的代码得到这个: 前面 -> [19] -> [4] -> [17] -> [8] -> [19] -> [1]/

不确定我做错了什么。

public void reverse(){
    int x = this.size();
    this.add(front.data);

    for (int i = 0; i < x; i++){
                this.remove(0);
        this.add(this.size()-1, front.data);
    }
}

// A LinkedIntList object can be used to store a list of integers.
public class LinkedIntList {
    private ListNode front;   // node holding first value in list (null if empty)
    private String name = "front";   // string to print for front of list

    // Constructs an empty list.
    public LinkedIntList() {
        front = null;
    }

    // Constructs a list containing the given elements.
    // For quick initialization via Practice-It test cases.
    public LinkedIntList(int... elements) {
        this("front", elements);
    }

    public LinkedIntList(String name, int... elements) {
        this.name = name;
        if (elements.length > 0) {
            front = new ListNode(elements[0]);
            ListNode current = front;
            for (int i = 1; i < elements.length; i++) {
                current.next = new ListNode(elements[i]);
                current = current.next;
            }
        }
    }

    // Constructs a list containing the given front node.
    // For quick initialization via Practice-It ListNode test cases.
    private LinkedIntList(String name, ListNode front) {
        this.name  = name;
        this.front = front;
    }

    // Appends the given value to the end of the list.
    public void add(int value) {
        if (front == null) {
            front = new ListNode(value, front);
        } else {
            ListNode current = front;
            while (current.next != null) {
                current = current.next;
            } 
            current.next = new ListNode(value);
        }
    }

    // Inserts the given value at the given index in the list.
    // Precondition: 0 <= index <= size
    public void add(int index, int value) {
        if (index == 0) {
            front = new ListNode(value, front);
        } else {
            ListNode current = front;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            } 
            current.next = new ListNode(value, current.next);
        }
    }

    public boolean equals(Object o) {
        if (o instanceof LinkedIntList) {
            LinkedIntList other = (LinkedIntList) o;
            return toString().equals(other.toString());   // hackish
        } else {
            return false;
        }
    }

    // Returns the integer at the given index in the list.
    // Precondition: 0 <= index < size
    public int get(int index) {
        ListNode current = front;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    // Removes the value at the given index from the list.
    // Precondition: 0 <= index < size
    public void remove(int index) {
        if (index == 0) {
            front = front.next;
        } else {
            ListNode current = front;
            for (int i = 0; i < index - 1; i++) {
                current = current.next;
            }
            current.next = current.next.next;
        }
    }

    // Returns the number of elements in the list.
    public int size() {
        int count = 0;
        ListNode current = front;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    // Returns a text representation of the list, giving
    // indications as to the nodes and link structure of the list.
    // Detects student bugs where the student has inserted a cycle
    // into the list.
    public String toFormattedString() {
        ListNode.clearCycleData();

        String result = this.name;

        ListNode current = front;
        boolean cycle = false;
        while (current != null) {
            result += " -> [" + current.data + "]";
            if (current.cycle) {
                result += " (cycle!)";
                cycle = true;
                break;
            }
            current = current.__gotoNext();
        }

        if (!cycle) {
            result += " /";
        }

        return result;
    }

    // Returns a text representation of the list.
    public String toString() {
        return toFormattedString();
    }

    // Returns a shorter, more "java.util.LinkedList"-like text representation of the list.
    public String toStringShort() {
        ListNode.clearCycleData();

        String result = "[";

        ListNode current = front;
        boolean cycle = false;
        while (current != null) {
            if (result.length() > 1) {
                result += ", ";
            }
            result += current.data;
            if (current.cycle) {
                result += " (cycle!)";
                cycle = true;
                break;
            }
            current = current.__gotoNext();
        }

        if (!cycle) {
            result += "]";
        }

        return result;
    }


    // ListNode is a class for storing a single node of a linked list.  This
    // node class is for a list of integer values.
    // Most of the icky code is related to the task of figuring out
    // if the student has accidentally created a cycle by pointing a later part of the list back to an earlier part.

    public static class ListNode {
        private static final List<ListNode> ALL_NODES = new ArrayList<ListNode>();

        public static void clearCycleData() {
            for (ListNode node : ALL_NODES) {
                node.visited = false;
                node.cycle = false;
            }
        }

        public int data;          // data stored in this node
        public ListNode next;     // link to next node in the list
        public boolean visited;   // has this node been seen yet?
        public boolean cycle;     // is there a cycle at this node?

        // post: constructs a node with data 0 and null link
        public ListNode() {
            this(0, null);
        }

        // post: constructs a node with given data and null link
        public ListNode(int data) {
            this(data, null);
        }

        // post: constructs a node with given data and given link
        public ListNode(int data, ListNode next) {
            ALL_NODES.add(this);
            this.data = data;
            this.next = next;
            this.visited = false;
            this.cycle = false;
        }

        public ListNode __gotoNext() {
            return __gotoNext(true);
        }

        public ListNode __gotoNext(boolean checkForCycle) {
            if (checkForCycle) {
                visited = true;

                if (next != null) {
                    if (next.visited) {
                        // throw new IllegalStateException("cycle detected in list");
                        next.cycle = true;
                    }
                    next.visited = true;
                }
            }
            return next;
        }
    }

// YOUR CODE GOES HERE

}

Answer 1

这是带有打印语句的代码:

public void reverse() {
  System.out.println(toFormattedString());

  int x = this.size();
  this.add(front.data);
  System.out.println(toFormattedString());

  for (int i = 0; i < x; i++) {
    this.remove(0);
    System.out.println(toFormattedString());
    this.add(this.size() - 1, front.data);
    System.out.println(toFormattedString());
  }
}

输出:

front -> [1] -> [2] -> [3] -> [4] -> [5] /
front -> [1] -> [2] -> [3] -> [4] -> [5] -> [1] /
front -> [2] -> [3] -> [4] -> [5] -> [1] /
front -> [2] -> [3] -> [4] -> [5] -> [2] -> [1] /
front -> [3] -> [4] -> [5] -> [2] -> [1] /
front -> [3] -> [4] -> [5] -> [2] -> [3] -> [1] /
front -> [4] -> [5] -> [2] -> [3] -> [1] /
front -> [4] -> [5] -> [2] -> [3] -> [4] -> [1] /
front -> [5] -> [2] -> [3] -> [4] -> [1] /
front -> [5] -> [2] -> [3] -> [4] -> [5] -> [1] /
front -> [2] -> [3] -> [4] -> [5] -> [1] /
front -> [2] -> [3] -> [4] -> [5] -> [2] -> [1] /

希望这对您有所帮助。