c++ - 不确定在单向链表中显示唯一数据

Question

我无法理解我应该怎么做才能打印单链表/线性链表中的所有唯一数据。

例如，如果我有以下数据会怎样:1 -> 1 -> 2 -> 3

在线性链表中，我必须打印 1 -> 2 -> 3

这是我的 SLL/LLL 节点结构代码。

struct node
{
     int data;
     node * next;
};

这是我添加它的代码

add(int data)
{
     if (!head)
     {
          head = new node;
          head -> data = data;
     }  
     else
     {
          add(head);
     }
}

add(node *& head)
 {
      if (!head)
      {
           return;
      }

      node * front = head -> next;

      if (!head -> next)
      {
           front = new node;
           front -> data = 
           head -> next = front;
           return;
      }

      add(head -> next);
}

这是我用来显示它的代码:

void displayUnique()
{
     if (!head)
     {      
          return;
     }

     return dU(head);
}

void dU(node * head)
{
     if (!head)
     {
          return;
     }

cout << head -> data << " ";

return dU(head -> next);
}

我应该对线性链表进行排序还是某种排序？

Answer 1

好的，所以有几种方法:

<强>1。列表的顺序无关紧要

如果顺序无关紧要，那么最快的方法是按 node.data 对列表进行排序。这给你 O(n*log n) 的复杂性。 (此外，如果是这种情况，我鼓励您修改 add(node *& head) 是它插入新 node 的方式，以保留列表排序)。之后，您可以跟踪之前显示的值并检查它是否相同。如果是，则跳到下一个节点。如果没有，显示当前的并记住你显示的内容。这是 O(n)。

<强>2。列表的顺序很重要

这里的问题有点复杂。您将需要额外的时间复杂度(不幸的是我的目标是 O(n^2))或额外的内存。我个人的方法是:创建临时的 std::set ，它会记住你已经显示的数字以及每次你遍历列表时(如果“遍历列表”不是valid term)，你会检查候选(当前node.data)是否已经显示，因此，记录在你的std::set中。搜索 std::set 是 O(n*log n)，所以它真的没那么糟糕(但是请记住，将一个值插入 set 需要更多时间时间比，例如，将值插入 std::vector)。

如果我遗漏了什么(明显或不明显)，请随时纠正或在评论中询问我。