我在java中使用一个链表，我需要获取一个x对象的列表，并将奇数位置的对象移动到列表的末尾。
我必须使用链接，没有新节点，没有列表数据交换。
当我把东西从一个列表移到另一个列表时，我觉得我有一个不错的处理方法，但遍历和附加对一个列表的引用真的很困难。
这是一个实际的问题——
编写一个方法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
}
这样看：
首先，我们需要某种光标，它将穿过列表并指向我们的"当前"节点
第二，我们需要一些布尔变量（我称之为INV）初始化为FALSE。。。每次我们移动列表中的节点时，我们都会反转INV
如果你从左边浏览列表，第二个元素是第一个被重新排列的元素，所以这将是我们的初始光标位置
让我们在该元素/节点上取一个引用，并将该引用作为中止条件
循环开始：
现在从列表中删除当前节点，并将其插入列表的末尾（移动到末尾…不是说光标可能不会随节点移动…）
将光标移动到我们刚刚移动的节点（如果存在）的前一位置右侧的节点
如果当前元素是我们的中止条件（我们移动的第一个元素），我们可以假设列表现在按所需顺序排序->我们完成了->退出循环。。。如果不是我们的中止标准。。。进行
将"光标索引为偶数"求值为TRUE或FALSE。。。与INV 异或
如果结果为TRUE，则将光标移动到下一个元素。。。如果为FALSE，则删除节点并将其插入末端（将其移动到末端）
循环
--
当我们浏览列表时，这种方法不会保留顺序，但当列表完成时，它会按所需顺序排列。。。
INV var用于补偿移除节点时的索引偏移。。。（0,1,2,3…如果你去掉1并把它放在最后，2将有一个奇数索引，所以如果我们每次移动都将其反转，我们就会得到"正确"的元素）