gpt4 book ai didi

java - 这个链表有什么问题?

转载 作者:搜寻专家 更新时间:2023-11-01 03:27:02 25 4
gpt4 key购买 nike

作业是编写一个函数来交换列表中的 2 个节点。如果函数可以不考虑顺序交换节点,则奖励 10%。我认为无论列表中的顺序如何,我的实现都能够交换 2 个元素,但我仍然没有收到奖励标记。有什么我想念的吗?

我得到了一个通用节点类,

public class Node<T> {
public T val;
public Node<T> next;

public Node(T val) {
this.val = val;
this.next = null;
}
}

我还得到了一个定义如下的接口(interface),

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);
}

我有自己的接口(interface)实现,如下所示,

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;
}

你看我没有在你的代码中添加行——而是我以另一种方式编写了代码。我认为它更具可读性,但您也可以尝试以正确的方式设置尾部。但它对我来说太复杂了,所以我降低了该代码的复杂性 - 这就是我重写它的原因。

我建议您将 first 和 second 用于第一次/第二次出现,而不是用于第一个/第二个参数。我认为这会提高方法的可读性。但这是另一点;-)

希望有帮助 - 所以恕我直言,顺序不是问题,而是尾部。

关于java - 这个链表有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11121525/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com