我正在尝试解决以下问题
编写一个方法拆分，用于重新排列列表的元素，以便所有负值都显示在所有非负值之前。 例如，假设变量列表存储以下值序列：
[8, 7, -4, 19, 0, 43, -8, -7, 2]
对list.split（）的调用应该重新排列列表以将负数放在首位。一种可能的安排如下：
[-4, -8, -7, 8, 7, 19, 0, 43, 2]
但重要的是，负数出现在非负片之前。 所以这只是一种可能的解决方案。另一个合法的解决方案是这样重新排列值：
[-7, -8, -4, 2, 43, 0, 19, 7, 8]
不允许交换数据字段或创建任何新节点来解决此问题; 您必须通过重新排列列表的链接来重新排列列表。 您也不能使用辅助结构（如数组，ArrayLists，堆栈，队列等）来解决此问题。
我真的不知道如何解决这个问题。我正在考虑的一种方法是识别具有负数据的节点并将其添加到头部，但我无法弄清楚如何编写这种方法。这是我的列表类。
public class LinkedList {
// The Linked List's Node structure
static class Node {
private Node next;
private int data;
Node(int data) {
this.data = data;
next = null;
}
public int getData() {
return data;
}
public void setNext(Node next) {
this.next = next;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
}
private Node head;
private int size;
public void setHead(Node head) {
this.head = head;
}
public int getSize() {
return size;
}
public Node getHead() {
return head;
}
public LinkedList() {
head = null;
size = 0;
}
}
解决这个问题有什么提示/建议吗？
正如@nishu所建议的，我想出了以下解决方案。它有效。
public Node delete(int data) {
Node del = null;
Node tmp = head;
if (head.getData() == data) {
Node tmp2 = head;
Node nxt = tmp.getNext();
tmp2.setNext(null);
this.setHead(nxt);
del = tmp2;
} else if (isLast(data)) {
while (true) {
if (tmp.getNext().getNext() == null) {
del = tmp.getNext();
tmp.setNext(null);
break;
}
tmp = tmp.getNext();
}
} else {
while (tmp != null && tmp.getNext() != null) {
if (tmp.getNext().getData() == data) {
Node prev = tmp;
del = tmp.getNext();
Node nextOfToBeDeleted = tmp.getNext().getNext();
prev.setNext(nextOfToBeDeleted);
break;
}
tmp = tmp.getNext();
}
}
return del;
}
public void addToFront(Node node) {
node.setNext(head);
this.setHead(node);
}
public void split() {
Node tmp = head;
Node del = null;
while (tmp != null) {
if (tmp.getData() < 0) {
Node nxt = tmp.getNext();
del = delete(tmp.getData());
addToFront(del);
while (tmp != nxt) {
tmp = tmp.getNext();
}
} else {
tmp = tmp.getNext();
}
}
}
public boolean isLast(int data) {
boolean last = false;
Node tmp = head;
while (true) {
if (tmp.getData() == data && tmp.getNext() != null) {
last = false;
break;
} else if (tmp.getNext() == null && tmp.getData() == data) {
last = true;
break;
}
tmp = tmp.getNext();
}
return last;
}
按照以下步骤继续操作：
-
创建方法：插入和删除。 插入 - 它将在开头插入数据。 delete - 它将搜索传递的值并删除列表中第一个出现的项，并返回已删除的节点。
-
开始遍历链表。每当找到负节点时，将其从现有链表中删除，并在删除函数返回的节点上调用插入方法。
向节点类型添加新接口：
static Node<T> implements Iterable<Node<T>> {
private Node<T> next;
private T data;
public T getData() {return data;}
public void setData(int data) {this.data = data;}
public Node getNext() {return next;}
public void setNext(Node<T> next) {this.next = next;}
}
然后，NodeIterator可以是
NodeIterator<E extends Node<T>, L extends LinkedList<T>> implements Iterator<E>{
E last, current; L parent;
public NodeIterator(E node, L parent){this.current = node; this.parent = parent;}
@Override public boolean hasNext(){return current.getNext() != null}
@Override public E next(){last = current; current = current.getNext(); return last;}
@Override public void remove(){last.setNext(current = current.getNext()); parent.size--;}
}
现在您已经有了这个，你可以编写移动列表的方法：
public class LinkedList<E> {
private Node<E> head;
private int size;
public void insertAtHead(Node<E> node){
node.setNext(head);
head=node;
size++;
}
public void split(Predicate<E> condition){
Iterator<Node<E>> it = nodeIterator();
while(it.hasNext()){
Node<E> node = it.next();
if(condition.test(node.getData())){
it.remove();
insertAtHead(node);
}
}
}
public Iterator<Node<E>> nodeIterator() {
return new NodeIterator<Node<E>, LinkedList<E>>(parent, head);
}
}
像这样调用：
LinkedList<Integer> list = new LinkedList<>();
// [... add stuff to list ...]
list.split((Integer i) -> i < 0);
编辑：修复了代码，以便在调用迭代器的 remove 函数时正确更新列表的大小。（不过，仍然仅适用于一个列表中包含的节点。如果两个列表实例包含相同的节点，并且删除了其中一个共享节点，则只有一个列表实例会更新其大小。
对于那些偶然发现这个寻求帮助来解决他们的实践 - IT问题的人，我在实践中做了同样的问题，这就是通过所有测试的原因：
public void split() {
ListNode temp = front;
for (int i = 0; i < this.size; i++) {
if (temp.data < 0) {
this.add(0, temp.data);
this.remove(i + 1);
}
temp = temp.next;
}
}
这个想法是我们创建指向linkedlist前面的"temp"变量，我们的 for 循环帮助我们按顺序迭代linkedlist中的所有索引位置。 我们的 "if" 条件测试整数是否为负数，如果是，那么我们要先将此数字添加到列表的前面， 然后从我们找到它的地方删除它。这个顺序很重要，因为如果我们先删除，我们就会丢失它，除非我们先将其保存到变量中，但这种方法更简单。我们对 add（） 方法的调用告诉它将我们当前指向的值添加到索引 0，也就是我们linkedlist的前面。一旦我们这样做了，我们就会突然指向我们指向的值之前的值，因为我们将列表的大小增加了一个，还没有增加我们的 for 循环变量值，所以当我们调用 remove() 方法时，我们传递给它的索引必须比我们的 for 循环变量 I 当前设置的值大 1， 所以我们的索引是i + 1.我们必须通过将 temp 等于 temp.next 将我们的 temp 变量移动到下一个节点，并且我们必须在 for 循环之外执行此操作，因为无论我们指向的值是否为负，我们都会这样做。我们的 for 循环测试不能等于linkedlist的大小，因为索引从 0 开始，所以我们的测试设置为我们的 I 是否小于我们linkedlist的大小。这是我能想到的最直接的方法，利用 Practice-It 提供的 LinkedIntList 类的内置方法。不确定这是否是您遇到问题的地方，但如果不是，我相信您将能够根据您正在使用的内容应用该策略。