2

我正在审查即将进行的测试的一些代码片段。我在笔记中看到了这一点，现在才意识到，如果列表以这种方式 A -> B -> C -> A，则方法 1 的代码实际上不会删除重复项。我写了一个替代函数（方法 2）我认为实际上会起作用。你们有什么感想？方法1实际上不起作用，我追踪它是错误的吗？ps 目前我们不允许编译器 :)

这是代码，以及它应该做什么的简短介绍。

方法1：当头部和尾部有2个确切的东西时，我认为不起作用。编写代码以从没有缓冲区的未排序列表中删除重复项。Wwe 可以使用两个指针进行迭代：“current”进行正常迭代，而“runner”迭代所有先前的节点以检查重复。Runner 每个节点只会看到一个副本，因为如果有多个副本，它们已经被删除了。

public static void deleteDuplicates1(LinkedListNode head) {
if (head == null) return;
LinkedListNode previous = head;
LinkedListNode current = previous.next;
while (current != null) {
    LinkedListNode runner = head;
       while (runner != current) { // Check for earlier dups
          if (runner.data == current.data) {
              LinkedListNode tmp = current.next; // remove current
              previous.next = tmp;
              current = tmp; // update current to next node
              break; // all other dups have already been removed
              }
              runner = runner.next;
          }
          if (runner == current) { // current not updated - update now
               previous = current;
               current = current.next;
              }
         }
 }

我在想这会奏效。方法二：

    public void removeDuplicates2(){  
    Node current = null;  
    Node tracer = null;  

   for( current = head.next; current!=null; current=current.next){  
       for(tracer=head; tracer!=current; tracer=tracer.next){  
          if(tracer.data == current.data)  
          //DELETE THE NODE IN CURRENT  
       }  
    }  

}
4

5 回答 5

9

最好的方法是对链表进行排序。然后迭代并检查相邻元素是否相同。如果是，则删除相邻元素。这是一个 O(nlogn) 方法，不使用额外的缓冲区。

于 2011-01-02T17:59:34.670 回答
6

我不确定“没有额外缓冲区”对您意味着什么，但由于我是一个懒惰的人，而且我认为其他人在写出算法方面比我好得多，所以我会将整个链表放入一个HashSet 并返回到一个链表。这将轻松删除重复项：

LinkedList result = new LinkedList(new HashSet(inputList));

或者，如果您想保留元素的顺序

LinkedList result = new LinkedList(new LinkedHashSet(inputList));

现在，由于这是一个家庭作业问题，而且您似乎自己正在实现一个 LinkedList，所以这个解决方案很可能是不可行的；-) 但无论如何，它的复杂性是 O(n)，而不是 O(n ^2) 喜欢你的方法 1 和 2，这对你来说可能已经好很多了......？

于 2011-01-02T15:21:57.963 回答
2

我在这里添加了我的代码，但我对时间复杂度是 O(n) 还是 O(nlogn) 感到困惑？让我知道这件事。

public Node removeDuplicatesFromUnsortedLinkedListWithoutExtraSpace(Node head)
{
    if(head == null || head.next == null)
        return head;

    Node prev = head;
    Node curr = head.next;
    Node temp = curr;

    while(prev.next!=null)
    {
        if(prev.data == curr.data)
        {
            temp.next = curr.next;
            curr = curr.next;
        }
        else
        {
            if(curr != null)
            {
                temp = curr;
                curr = curr.next;
            }

            if(curr == null)
            {
                prev = prev.next;
                curr = prev.next;
                temp = curr;
            }
        }
    }
    return head;
}
于 2014-02-14T22:05:40.010 回答
0

对上述函数进行了修改以纠正逻辑但我不确定该函数的时间复杂度是多少。是 O(n^2) 还是 O(n)

public static Node removeDuplicatesFromUnsortedLinkedListWithoutExtraSpace(Node head){ if(head == null || head.next == null) return head;

    Node prev = head;
    Node curr = head.next;
    Node temp = prev;

    while(prev.next!=null){
        if(curr != null){
            if(prev.data == curr.data){
                temp.next = curr.next;
                curr = curr.next;
            }else {
                temp = curr;
                curr = curr.next;
            }
        }else{
            prev = prev.next;
            curr = prev.next;
            temp = prev;
        }
    }
    return head;
}
于 2014-08-11T18:37:28.143 回答
0 
public static Node removeDuplicates(Node head) {
    Node cur = head;
    Node next = cur.next;
    while (cur != null && cur.next != null) {
        next = cur;
        while (next.next != null) {
            if (cur.data == next.next.data) {
                Node d = next.next;
                next.next = next.next.next;
            } else {
                next = next.next;
            }
        }
        cur = cur.next;
    }
    return head;
}

这使用双指针方法。在不使用任何额外空间的情况下，我们可以有两个点 cur(Slow) 和 next(Fast) 指针。对于每个 cur 指针，检查下一个指针中的数据。如果找到匹配项，则调整指针以指向下一个相应节点。希望这可以帮助。

于 2017-03-14T20:06:16.740 回答