Java双链表——两个相邻节点的相等性

Question

一个公共方法 twoTogether(( for the class MyList 返回 True，当且仅当列表有两个相邻元素相等时。您可以假设没有列表元素(数据(为空。下面是一些示例：调用此方法时，列表 [a，b，c，d] 将返回 false。但是一个列表 [a，b，b，c] 或 [a，b，c，d，e，f，f]。该方法返回 true。一起编写公共方法。您可以使用列表接口引用(字段：数据，上一个，下一个((头，尾((大小(等。这是我编写的代码：

 public boolean twoTogether(){
      currentNode = head;
      while (currentNode.hasNext()){ 
            if (currentNode.data != currentNode.next.data){ 
                  currentNode = currentNode.next;
            }
            else if (currentNode.data == currentNode.next.data){
                 return True;
            }
      }
      return False;
  }

此代码是否正确遍历两个节点之间相等性的列表测试？我也正确地实现了 hasNext(( 吗？我很难弄清楚如何不终止循环，或者为嵌套的 if 返回 true，然后为 else 语句返回 false。

Answer 1

你是对的，循环终止并不完全正确。while 循环中的前两个分支不属于。前两个分支之一将始终触发，因为 ！= 和 == 是补语。return false 语句属于 while 循环之外，表示已遍历整个列表并且没有相等的相邻节点。

public boolean twoTogether(){
    currentNode = head;
    while (currentNode.hasNext()){ 
        if (currentNode.data != currentNode.next.data){ 
            currentNode = currentNode.next;
        }
        else if (currentNode.data == currentNode.next.data){
            return True;
        }
    }
    return False;
}

hasNext(( 的使用是完美的！ 永远不想过度遍历列表...希望这有帮助！

Answer 2

基本思想如下：

• 第一步，检查列表是否为空。如果是这种情况，那么根据定义，不可能有重复项，因此返回false并停止。
  
  这可以防止您在当前元素不存在时尝试计算以下元素(。
  
  否则，从当前元素作为列表中的第一个元素开始。

• 第二步，只要当前元素后面至少还有一个元素，您就需要继续(因为您想检查当前元素与下一个元素(。
  
  如果没有以下元素，那么您已经完成了列表并且没有找到重复项，因此请立即返回false(因此停止(。

• 第三步，您现在知道当前和下一个，因此实际上检查当前与下一个。
  
  如果他们的数据相同，则您已经找到了重复项，您可以立即返回true(因此停止(。

第四步，此时没有重复项，

• 但可能还有一个重复项，因此请前进到下一个元素并返回上面的第二步以重新检查您是否已到达终点。

这样做的伪代码将是(传入head作为参数(：

def twoTogether (node):
    if node == null:                     # empty means no dupes possible
        return false
    while node.next != null:             # loop through list
        if node.data == node.next.data:  # check current against next
            return true
        node = node.next                 # advance to next
    return false                         # no dupes before list end