這個鏈表有什麼問題？

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

你看，我沒加行代碼 - 而不是我寫的代碼以另一種方式。我認爲它更具可讀性，但您也可以嘗試以正確的方式設置尾部。但對我來說太複雜了，所以我減少了代碼的複雜性 - 這就是我重寫它的原因。

我會建議，你使用第一次和第二次的第一次/第二次發生，而不是第一次/第二次參數。我認爲這會提高該方法的可讀性。但這是另一個點;-)

希望幫助 - 所以恕我直言的順序不是問題，但尾巴。