LinkList，檢查雙值

Question

我正在寫一個代碼，如果整個鏈接列表結束，則返回true，否則返回false。一個結巴的名單將是1,1,2,2,5,5,8,8，非結巴將是像1,1,2,2,5,6,8,8。

我一直在玩弄它相當長一段時間，似乎並不能得到它返回正確的語句或無法獲得空指針異常。

public boolean foo(){ 
    ListNode current = front; 
    ListNode runner = current.next; 
    while (current.next.next!=null){ //Looks two ahead for the end 
     if(current.data!=runner.data){  //They aren't equal, false 
      System.out.println(current.data); //just to see my data 
      System.out.println(runner.data); //debugging only 
      return false; 
     } 
     current = current.next.next; //increase by 2 
     runner = runner.next.next; // increase by 2 
     System.out.println(current.data + " ||" + runner.data); //again debugging 
    } 
    return true; // didn't register false, go ahead and true dat badboy. 
} 


    public static void main (String[] args){ 
    LinkedIntList list = new LinkedIntList(); 
    list.add(1); 
    list.add(1); 
    list.add(3); 
    list.add(3); 
    list.add(5); 
    list.add(5); 
    System.out.println(list.foo()); 
} 

有人在這裏看到明顯的錯誤嗎？我試過運行我的while循環current.next，以及增加我的跑步者和當前每次一個而不是兩個，但沒有任何工作。

Answer 1

代替while (current.next.next!=null)，檢查while (runner.next!=null)。此外，您必須匹配while循環後的最後兩個節點的數據。

假設列表中包含偶數個元素，就像您在問題中提到的那樣，代碼中的以下更改將產生正確的輸出。

public boolean foo(){ 
    ListNode current = front; 
    ListNode runner = current.next; 
    while (runner.next!=null){ //Looks two ahead for the end 
     if(current.data!=runner.data){  //They aren't equal, false 
      System.out.println(current.data); //just to see my data 
      System.out.println(runner.data); //debugging only 
      return false; 
     } 
     current = current.next.next; //increase by 2 
     runner = runner.next.next; // increase by 2 
     System.out.println(current.data + " ||" + runner.data); //again debugging 
    } 
    if(current.data!=runner.data){  //They aren't equal, false 
     System.out.println(current.data); //just to see my data 
     System.out.println(runner.data); //debugging only 
     return false; 
    } 
    return true; // didn't register false, go ahead and true dat badboy. 
} 

---

更好&乾淨實現如下：

public boolean foo(){ 
    ListNode current = front; 
    while (current != null){ 
     if(current.next == null) 
      return false; 
     if(current.data != current.next.data) 
      return false; 
     current = current.next.next; 
    } 
    return true; 
} 

Answer 2

不能盲目使用current.next.next沒有一些檢查第一，因爲它是完全可能的，無論是current或current.next將是無效的。

如果是這樣，你會得到一個空指針的問題。

假設口吃的裝置僅兩倍（根據你的例子），而不是任何倍數，它可以更好向下以下算法：

def isStuttered(node): 
    while node != null: 
    # Check if only one item left. 

    if node.next == null: 
     return false 

    # Check if not a pair. 

    if node.data != node.next.data: 
     return false 

    # Advance to next pair, okay as we have 2+ items left. 

    node = node.next.next 

    return true 

stuttered = isStuttered(head) 

---

順便說一句，如果「口吃」意味着兩件以上每一個項目，這是一個小的變化的算法：

def isStuttered(node): 
    while node != null: 
    # Check if only one item left. 

    if node.next == null: 
     return false 

    # Check if not at least two. 

    val = node.data 
    if val != node.next.data: 
     return false 

    # Start with second item in set, 
    # advance to either new value or list end. 

    node = node.next 
    while node != null  # note 'and' must short-circuit 
    and node.data == val: 
     node = node.next 

    return true