algorithm - 如何在不使用任何额外内存的情况下从 unicode 字符的链接列表中消除重复项

Question

“在 unicode 字符的链表中查找重复出现的元素。如果发现一个 unicode 字符/s 有重复，则只需删除该重复节点并调整列表。限制是不使用任何额外的内存。”</p>

我的回答：
假设 unicode char 不包括代理对 char 因为我正在使用 c#

我不知道如何找到重复字符，除非您在遍历列表时知道先前节点的值，并且要维护先前的值，您将需要额外的内存（哈希表）。

小伙伴们，你们能想出什么办法来解决这个问题吗？这是其中一个网站上的面试问题。也有可能在 O(n) 时间内解决这个问题吗？
这是我的实现。你能提供反馈，以便我可以做得更好吗？

public static void RemoveDup(Node head)
        {
            Node current1 = head;
            Node current2;



            while (current1 != null)
            {
                current2 = current1;
                while (current2 != null)
                {
                    if (current2.Next!=null && current1.Data == current2.Next.Data)
                    {
                        Node temp = current2.Next.Next;
                        current2.Next = temp;
                        current2=current1;
                        continue;                        
                    }

                    current2 = current2.Next;
                    if (current2 == null)
                        break;

                }

                current1 = current1.Next;
                if (current1 == null)
                    break;
            }


        }

Answer 1

对于列表中的每个元素，在列表中搜索该元素并从该元素的位置开始将其删除，直到您没有元素为止。

我将把实施和其他选择留给你。

Answer 2

对列表进行排序 - 然后所有重复项将排成一行。这将花费 O(nlogn) 时间。当然，这假设您可以对列表进行排序（也许顺序很重要？）并且您可以就地对其进行排序（没有额外的内存）。

Answer 3

在不以某种方式保存以前看到的值的情况下，我能看到的唯一方法是使用嵌套循环。外循环是“遍历整个列表”，内循环是“遍历整个列表并删除外循环指向的项目的副本”。