LinkList, проверка на двойные значения

Question

Я пишу код, который возвращает true, если весь список ссылок заштрихован и false, если это не так. Заикаемым списком будет 1,1,2,2,5,5,8,8, без заикания будет что-то вроде 1,1,2,2,5,6,8,8.

Я довольно долго играл с ним и не могу заставить его вернуть правильное утверждение ИЛИ не получить исключение nullpointer.

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