删除重复链表 Java

Question

我正在尝试实现一种从链表中删除所有重复项的方法。我已经设法照顾好尾巴了。换句话说，如果尾部的 data 重复，程序就不会抛出 exception error。现在，我正在尝试处理 head，如果 head 的数据重复，我想设置 head = head.next 以便不重复在链表中更长。但是我的方法 deleteDuplicates 不处理 head。有人有解决此问题的建议吗？

class Node {
        private Node next = null; 
        private int data; 

        public Node(int d) {
            data = d; 
        }

        void appendToTail(int d) {
            Node end = new Node(d); 
            Node n = this; 

            while(n.next != null) {
                n = n.next; 
            }
            n.next = end; 
        }

        void print() {
            Node n = this; 
            while(n != null) {
                System.out.println(n.data); 
                n = n.next; 
            }
        }

        Node deleteDuplicates(Node head, int d) {
            Node n = head;
            if(n.data == d) {
                head = head.next; 
                n = n.next; 
            }
            while(n != null) {
                if(n.next.data == d) {
                    if(n.next == null && n.next.data == d) {
                        return head;
                    }
                    n.next = n.next.next;
                }
                n = n.next; 
            }
            return head; 
        }

        public static void main(String [] args) {
            Node x = new Node(9); 
            x.appendToTail(5);
            x.appendToTail(9);
            x.appendToTail(6);
            x.appendToTail(9);  
            x.appendToTail(7);
            x.appendToTail(9);  
            x.appendToTail(8); 
            x.appendToTail(9); 
            x.deleteDuplicates(x, 9); 
            x.print(); 
        }   
    }

Answer 1

如果您只需要一个唯一对象的容器，最好的方法是让这些对象实现 .equals() 和 .hashCode() 方法，这样您就可以使用 Set 来处理唯一性逻辑。

相等性可以很容易地实现为所有 class' 字段相等性的添加，以及来自所有 class' 字段 hashCodes 的串联散列的 hashCode。

如果您出于某种原因需要链接它们，LinkedHashSet 可以满足您的需求。

整数示例：

LinkedHashSet<Integer> myCollection = new LinkedHashSet<Integer>();
myCollection.add(5);
myCollection.add(3);
myCollection.add(2);
myCollection.add(5);
myCollection.add(2);
System.out.println(myCollection);
// prints [5, 3, 2]

可以找到带有自定义 class 的示例 here。

Answer 2

你的代码中的问题是你没有在删除后重新分配你的头。如果按如下方式修改，我想你的删头问题就迎刃而解了。

x = x.deleteDuplicates(x, 9);

不用说，还有其他有效的方法，如散列，可用于降低代码的时间复杂度。

Answer 3

你想一直移除头部，只要它与值匹配。因此，将 if 替换为 while:

Node n = head;
while (n != null && n.data == d) {
    n = n.next; 
}
head = n;

你还有其他问题。例如，当 n.next 为空时，此行将引发空指针异常：

if(n.next == null && n.next.data == d) {

修复你的 while 循环：

while (n.next != null) {
    if (n.next.data == d) {
        n.next = n.next.next;
    } else {
        n = n.next;
    }
}

最后，您选择的方法名称非常具有误导性。 "deleteDuplicates" 建议删除所有重复项，例如：

from: 9->5->6->9->7->9->8->9  
  to: 9->5->6->7->8

只调用此方法是有意义的 delete。

放在一起

应用上述更正后，方法变为：

Node delete(Node head, int d) {
    Node n = head;

    // skip consecutive d values at head
    while (n != null && n.data == d) {
        n = n.next; 
    }
    head = n;

    // skip d values
    while (n.next != null) {
        if (n.next.data == d) {
            n.next = n.next.next;
        } else {
            n = n.next;
        }
    }

    return head;
}

Answer 4

已通过运行代码验证。您的代码应如下所示：

x.deleteDuplicates(x, 9).print();

那么删除方法应该是：

Node deleteDuplicates(Node head, int d) {
    Node nextNode=head;
    if(head.data == d) {
        if(head.next==null) {
            return null;
        }
         return deleteDuplicates(head.next, d);
    }
    Node previous=head;
    while(nextNode.next != null) {
        nextNode=nextNode.next;
        if(nextNode.data == d) {
            previous.next=nextNode.next;
        }
        previous=nextNode;
    }
    return head;
}

输出：

在检查是否需要删除头节点时，将下一个节点作为头节点。您还检查是否要删除最后一个节点，然后将之前的节点设为 null。

Answer 5

类似于（未经测试的代码）：

想法是，对于每个元素，遍历列表的其余部分并删除当前元素的重复项

public void deleteDupes(Node head) {
  if (head == null || head.next == null) {
    return;
  }
  Node current = head;
  while (current != null) {
    Node runner = head;
    while (runner.next != null) {
      if (runner.next.val == current.val) {
        runner.next = runner.next.next;
      }
      else {
        runner = runner.next;
      }
    }
    current = current.next;
  }
}

删除重复链表 Java

Deleting duplicates a linked lists Java

java

linked-list

放在一起