java列表通过重新排列链接来移动项目

Question

我正在使用java中的链接列表，我需要获取x个对象的列表并将奇数位置的对象移动到列表的末尾。

我必须通过使用链接来做到这一点，没有新节点，没有 list.data 交换。

当我将内容从一个列表移动到另一个列表时，我觉得我有一个不错的处理能力，但是遍历和附加仅引用一个列表确实很困难。

这是实际问题 ---

编写一个方法 shift，通过将奇数位置的所有值移动到列表末尾并保留列表顺序来重新排列整数列表的元素。例如，假设变量列表存储以下值:

[0、1、2、3、4、5、6、7]list.shift()的调用；应将列表重新排列为:

[0、2、4、6、1、3、5、7]您必须通过重新排列列表的链接来解决此问题。

<小时/>

下面是我之前需要编写方法的类(具有上述限制。

我实在想不出攻击计划。

// 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

这样看:

首先我们需要某种光标来遍历列表并指向我们的“当前”节点

其次，我们需要一些初始化为 FALSE 的 boolean 变量(我称之为 INV)...每次我们在列表中移动节点时，我们都会反转 INV

如果从左侧浏览列表，第二个元素是第一个被重新排列的元素，因此这将是我们的初始光标位置

让我们获取该元素/节点的引用，并将该引用保留为中止标准

循环开始:

现在从列表中删除当前节点并将其插入到列表末尾(移动到末尾...并不是说光标不能随节点移动...)

将光标移动到我们刚刚移动的节点之前位置右侧的节点(如果存在)

如果当前元素是我们的中止标准(我们移动的第一个元素)，我们可以假设列表现在已按所需顺序排序 -> 我们完成 -> 退出循环...如果它不是我们的中止标准.. .继续

将“光标索引为偶数”评估为 TRUE 或 FALSE ...与 INV 进行异或

如果结果为 TRUE，则将光标移动到下一个元素...如果为 FALSE，则删除该节点并将其插入到末尾(将其移至末尾)

循环

--

当我们在列表中移动时，这种方法不会保留顺序，但在完成时会按所需的顺序排列列表...

INV var 用于补偿删除节点时索引的偏移...(0,1,2,3 ...如果删除 1 并将其放在末尾，2 将具有奇数索引，因此如果我们每一步都颠倒过来，我们就会得到“正确”的元素)