面试题:从未排序的链表中删除重复项 [英] Interview question: remove duplicates from an unsorted linked list

查看：19 发布时间：2022/1/1 18:37:09 c# java linked-list

本文介绍了面试题:从未排序的链表中删除重复项的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我正在阅读破解编码面试，第四版:150 个编程面试问题和解决方案，我正在尝试解决以下问题:

I'm reading Cracking the Coding Interview, Fourth Edition: 150 Programming Interview Questions and Solutions and I'm trying to solve the following question:

2.1 编写代码从未排序的链表中删除重复项.跟随UP:如果遇到这个问题，你会怎么解决?不允许使用临时缓冲区?

2.1 Write code to remove duplicates from an unsorted linked list. FOLLOW UP: How would you solve this problem if a temporary buffer is not allowed?

我正在用 C# 解决它，所以我创建了自己的 Node 类:

I'm solving it in C#, so I made my own Node class:

public class Node<T> where T : class
{
    public Node<T> Next { get; set; }
    public T Value { get; set; }

    public Node(T value)
    {
        Next = null;
        Value = value;
    }
}

我的解决方案是遍历列表，然后对每个节点遍历列表的其余部分并删除任何重复项(请注意，我并没有按照书中的说明实际编译或测试它):

My solution is to iterate through the list, then for each node to iterated through the remainder of the list and remove any duplicates (note that I haven't actually compiled or tested this, as instructed by the book):

public void RemoveDuplicates(Node<T> head)
{
    // Iterate through the list
    Node<T> iter = head;
    while(iter != null)
    {
        // Iterate to the remaining nodes in the list
        Node<T> current = iter;
        while(current!= null && current.Next != null)
        {
            if(iter.Value == current.Next.Value)
            {
                current.Next = current.Next.Next;
            }

            current = current.Next;
        }    

        iter = iter.Next;
    }
}

这里是书中的解决方案(作者用java写的):

Here is the solution from the book (the author wrote it in java):

没有缓冲区，我们可以迭代两个指针:当前"是否正常迭代，而runner"迭代通过所有先前的节点来检查重复.跑步者每人只会看到一个 dup节点，因为如果有多个他们本来是重复的已经删除了.

Without a buffer, we can iterate with two pointers: "current" does a normal iteration, while "runner" iterates through all prior nodes to check for dups. Runner will only see one dup per node, because if there were multiple duplicates they would have been removed already.

public static void deleteDups2(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;
        }
    }
}

所以我的解决方案总是寻找当前节点到最后的重复项，而他们的解决方案则寻找从头到当前节点的重复项.我觉得这两种解决方案都会遇到性能问题，具体取决于列表中有多少重复项以及它们的分布方式(密度和位置).但总的来说:我的答案是几乎和书中的答案一样好，还是明显更差?

So my solution always looks for duplicates for the current node to the end, while their solution looks for duplicates from the head to the current node. I feel like both solutions would suffer performance issues depending on how many duplicates there are in the list and how they're distributed (density and position). But in general: is my answer nearly as good as the one in the book or is it significantly worse?

面试题:从未排序的链表中删除重复项 [英] Interview question: remove duplicates from an unsorted linked list

问题描述

推荐答案

相关文章

Java开发最新文章

热门教程

热门工具

登录关闭

面试题:从未排序的链表中删除重复项 [英] Interview question: remove duplicates from an unsorted linked list

问题描述

推荐答案

相关文章

Java开发最新文章

热门教程

热门工具

登录 关闭

登录关闭