java - 从链接列表中删除重复项

Question

所以我有一个链接列表，我试图从中删除重复项。

我想出的基本算法是使用运行者技术。我保留两个指针来比较相邻元素。如果它们相同，我将 p1 的指针更改为指向 p1.next.next，如果不是，我继续遍历列表。但是，我在输入的解决方案中不断收到空指针异常。

Node RemoveDuplicates(Node head) {
  // This is a "method-only" submission. 
  // You only need to complete this method. 
    if (head == null){
        return null;
    } 

        Node current = head;
    Node runner = head;



    while(current != null && runner != null && runner.next != null){
    runner = runner.next;
    if(runner.data == current.data){
        if(current.next != null){
                    current = current.next.next; 

        }
    }else{
        current = current.next;
    }
}



    return current;
}

在我退出 while 循环时电流为空。我认为这就是问题所在。我将如何返回更改后的列表的头部。

Answer 1

好的，虽然您已经接受了答案，但这里有一些示例代码，使用递归根据您在评论中的请求从有序列表中删除重复项。 (如果您的列表未排序，请排序:))

public Node removeDups(Node root) {
    if (root.next == null)
        return root;
    root.next = removeDups(root.next);
    if (root.data == root.next.data)
        return root.next;
    return  root;
} // call as root = removeDups(root);

正如您所提到的，递归在这里并不是真正必要的，但您使用的是递归定义的基于节点的链表。因此，当有意义时，解决方案的优雅就有其好处。

我喜欢它的地方在于，您不需要执行任何 node.next.next 或需要检查 null 情况。一旦堆栈开始展开，您就可以开始检查重复项了。那么只需比较 root.data 和 root.next.data 即可；您已经知道这两者都存在。