任务是编写一个函数来交换列表中的 2 个节点。如果函数可以交换节点，而不管顺序如何，则奖励 10%。我认为无论列表中的顺序如何，我的实现都可以交换 2 个元素，但我仍然没有收到奖励标记。我错过了什么吗？
我得到了一个通用节点类，
public class Node<T> {
public T val;
public Node<T> next;
public Node(T val) {
this.val = val;
this.next = null;
}
}
我还得到了一个定义如下的接口，
public interface SwapList<T> {
public void add(T val);
/**
* Swaps two elements in the list, but only if @param val1 comes BEFORE @param
* val2. Solve the problem regardless of the order, for 10% extra. list: A B
* C -> swap(A,B) will result in the list B A C list: A B C -> swap(B,A)
* will not swap. list: A C C -> swap(A, D) will throw a
* NoSuchElementException list: A B C B -> swap (A, B) will result in the
* list B A C B list: A B C A B B -> swap (A,B) will result in the list B A
* C A B B a list with one or zero elements cannot do a swap
*/
public void swap(T val1, T val2);
public T get(int i);
}
我有自己的这个接口的实现，如下所示，
import java.util.NoSuchElementException;
public class SwapListImpl<T> implements SwapList<T> {
private Node<T> head;
private Node<T> tail;
private int counter;
public SwapListImpl() {
head = null;
tail = null;
counter = 0;
}
@Override
public void add(T val) {
Node<T> node = new Node<T>(val);
if (head == null) {
head = node;
tail = node;
} else {
tail.next = node;
tail = node;
}
counter++;
}
@Override
public void swap(T val1, T val2) {
if (counter < 2 || val1.equals(val2))
return;
Node<T> current = head;
Node<T> currentPrev = null;
Node<T> first = head;
Node<T> firstPrev = null;
Node<T> firstNext = first.next;
Node<T> second = head;
Node<T> secondPrev = null;
Node<T> secondNext = second.next;
boolean foundFirst = false;
boolean foundSecond = false;
boolean inOrder = false;
while (current != null) {
if (!foundFirst && current.val.equals(val1)) {
firstPrev = currentPrev;
first = current;
firstNext = current.next;
if (!foundSecond)
inOrder = true;
foundFirst = true;
}
if (!foundSecond && current.val.equals(val2)) {
secondPrev = currentPrev;
second = current;
secondNext = current.next;
if (foundFirst)
inOrder = true;
foundSecond = true;
}
if (foundFirst && foundSecond) {
if (!inOrder) {
Node<T> temp = first;
first = second;
second = temp;
temp = firstPrev;
firstPrev = secondPrev;
secondPrev = temp;
temp = firstNext;
firstNext = secondNext;
secondNext = temp;
}
if (firstPrev == null) {
head = second;
if (first == secondPrev) {
second.next = first;
first.next = secondNext;
} else {
second.next = firstNext;
secondPrev.next = first;
first.next = secondNext;
}
} else {
firstPrev.next = second;
first.next = secondNext;
if (first == secondPrev) {
second.next = first;
} else {
second.next = firstNext;
secondPrev.next = first;
}
}
break;
}
currentPrev = current;
current = current.next;
}
if (!foundFirst || !foundSecond) {
throw new NoSuchElementException();
}
}
@Override
public T get(int i) {
if (i < counter) {
Node<T> node = head;
for (int n = 0; n < i; n++) {
node = node.next;
}
return node.val;
} else {
throw new IndexOutOfBoundsException();
}
}
}
我认为
问题在于交换本身：您忘记设置尾巴。
这是针对该问题的一个小测试：
@Test
public void test() {
SwapListImpl<String> list = new SwapListImpl<String>();
list.add("A");
list.add("B");
list.add("C");
list.swap("A", "C");
assertEquals("C", list.get(0));
assertEquals("C", list.getHead().val);
assertEquals("B", list.get(1));
assertEquals("A", list.get(2));
assertEquals("A", list.getTail().val);
list.add("D");
assertEquals("C", list.get(0));
assertEquals("C", list.getHead().val);
assertEquals("B", list.get(1));
assertEquals("A", list.get(2));
assertEquals("D", list.get(3));
assertEquals("D", list.getTail().val);
list.swap("A", "C");
assertEquals("A", list.get(0));
assertEquals("A", list.getHead().val);
assertEquals("B", list.get(1));
assertEquals("C", list.get(2));
assertEquals("D", list.get(3));
assertEquals("D", list.getTail().val);
list.swap("C", "B");
assertEquals("A", list.get(0));
assertEquals("A", list.getHead().val);
assertEquals("C", list.get(1));
assertEquals("B", list.get(2));
assertEquals("D", list.get(3));
assertEquals("D", list.getTail().val);
}
你看我在列表中添加了两个方法，用于获取头部和尾部，但这并不重要 - 如果没有对头部和尾部的显式测试，测试甚至会失败。列表的额外方法非常简单：
public Node<T> getTail() {
return this.tail;
}
public Node<T> getHead() {
return this.head;
}
交换列表的最后一个元素然后添加另一个元素时，会出现不设置 tail 的问题。
以下是实际交换的固定版本：
if (foundFirst && foundSecond) {
if (second == this.tail) {
this.tail = first;
} else if (first == this.tail) {
this.tail = second;
}
if (first == this.head) {
this.head = second;
} else if (second == this.head) {
this.head = first;
}
if (firstPrev == second) {
first.next = second;
} else {
if (firstPrev != null) {
firstPrev.next = second;
}
first.next = secondNext;
}
if (secondPrev == first) {
second.next = first;
} else {
if (secondPrev != first && secondPrev != null) {
secondPrev.next = first;
}
second.next = firstNext;
}
break;
}
你看我没有在你的代码中添加行 - 相反，我以另一种方式编写代码。我认为它更具可读性，但您也可以尝试以正确的方式设置尾巴。但它对我来说太复杂了，所以我降低了代码的复杂性 - 这就是我重写它的原因。
我建议，您将第一个和第二个用于第一次/第二次出现，而不是用于第一个/第二个参数。我认为这将提高该方法的可读性。但这是另一点;-）
希望有帮助 - 所以恕我直言，订单不是问题，而是尾巴。