这个链表有什么问题？

Question

该任务是编写一个函数来交换列表中的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(); 
     } 
    } 
} 

Answer 1

我觉得问题是交换本身：你忘了设置尾部。

这里正是出于这个问题的一个小测试：

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

不设置尾的问题交换列表的最后一个元素时，再加入另一种元素出现。

下面是实际的交换的一个固定的版本：

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

你看，我没加行代码 - 而不是我写的代码以另一种方式。我认为它更具可读性，但您也可以尝试以正确的方式设置尾部。但对我来说太复杂了，所以我减少了代码的复杂性 - 这就是我重写它的原因。

我会建议，你使用第一次和第二次的第一次/第二次发生，而不是第一次/第二次参数。我认为这会提高该方法的可读性。但这是另一个点;-)

希望帮助 - 所以恕我直言的顺序不是问题，但尾巴。