0

我正在使用 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

}
4

1 回答 1

1

这样看:

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

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

如果你从左边遍历列表,第二个元素是第一个被重新排列的元素,所以这将是我们的初始光标位置

让我们对该元素/节点进行引用,并将该引用保留为中止标准

循环开始:

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

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

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

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

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

做循环

--

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

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

于 2012-08-03T03:13:46.107 回答