在链表中保持相同长度的重复元素的建议

Question

我正在用c++处理一个文本文档，对于一些解析，链表由重复的元素组成，作为文档的"单词"。

现在，我需要一种算法来排序这个链表，使重复元素到中间的距离相等，但方向相反。中间元素为MARK元素。

Original Linked List:-
Head-> A-B-A-C-C-D-E-F-E-F-D-B (Size 12)
Processed Linked List:-
Head-> A-B-C-D-E-F-MARK-F-E-D-C-B-A (Size 13 = 12 + MARK)

有什么想法吗?

Answer 1

如果存在偶数，则可以按值对列表进行排序，并创建一个大小为+1的新列表，在中心添加MARK。

:

//Iterate over the list, but process both the original and the duplicate at the same time.
for(i = 0; i < (original_list.size()/2); i++)
{
    //First element
    new_list[i] = original_list[i*2]
    //Duplicate element
    new_list[new_list.size() - i] = original_list[(i*2)+1]
}

Answer 2

如果元素至少重复一次。那么你可以使用下面的算法
算法的复杂度为O(n)，但在新链表中插入节点的复杂度为O(nlogn)
解析链表中的每一次传递，从linkedList中拔出当前节点，并将它们添加到两个新的linkedList中(一个按升序排列，另一个按降序排列)，最后在升序链表的末尾添加新节点"MARK"，现在连接两个新创建的链表。
HashMap仅用于处理惟一值(意味着不考虑重复值)

下面是相同的JAVA代码，很抱歉我不能提供c++的代码(因为我不懂c++: p)
但我已经尽力提供了尽可能多的评论，这样你就可以得到一个想法
我将列表视为具有头和尾的双链表
Node具有以下结构

class Node
{
  String data;
  Node next, prev;
}

下面的代码具有创建处理过的链表所需的方法和排序函数

public Node getHead()
{
    return this.head;
}
public void setHead(Node n)
{
    this.head = n;
}
public Node getTail()
{
    return this.tail;
}
public void setTail(Node n)
{
    this.tail = n;
}
public void addLast(Node n)
{
    // Adds the node to the last of the list
    // in such a way that the inserted node will
    // be sorted in increasing order
}
public void addFirst(Node n)
{
        // Adds the node to the first of the list
        // in such a way that the inserted node will
        // be sorted in non-increasing order
}
public Node sort(Node head)
{
    Node n = head;
    HashMap<String, Boolean> map = new HashMap<String, Boolean>();
    LinkedList asc = new LinkedList();
    LinkedList des = new LinkedList();
    // Parse the linked list
    while(n!=null)
    {
    if(!map.containsKey(n.data))
    {
            // Remove the n from the Current Linked List
        delete(n);
        map.put(n.data);
        // Add in the new linked List
            asc.addLast(n);
            desc.addFirst(n);
            n = n.next;
    }
    }
    // Add new Node Mark to the end of the asc list
    asc.addLast(new Node("MARK"));
    // Join asc list to the desc list
    asc.getTail().next = desc.getHead();
    // Making head and tail as null as it is now combined with ASC list
    // If you do not do it then it may leads to memory leak
    // in deletion of nodes from processed list
    desc.setHead(null);
    desc.setTail(null);
    // Return the head of new processed list
    return asc.getHead();
}
public void delete(Node n)
{
    if(n==null)
        return;
    if(head==n)
    {
        // If the node to delete is head
        head = head.next;
    }
    else if(head==null)
    {
        // If the node to delete is tail
        tail = tail.prev;
    }
    else
    {
        // If the node to delete is present in the middle
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }
    n.next = n.prev = null;
}

注意
如果值不重复，那么它将创建重复元素，因为每个节点被添加到两个链表中，最终合并

Answer 3

假设列表中的所有元素只重复一次，您可以使用这种方法。

#include <list>
#include <iterator>
#include <iostream>
#include <algorithm>
int main (int argc, char* argv[])
{
    char data[] = {'A', 'B', 'A', 'C', 'C', 'D', 'E', 'F', 'E', 'F', 'D', 'B'};
    std::list<char> c( data, data + sizeof(data) / sizeof(char) );
    // Remove all duplicates
    c.sort();
    std::list<char>::iterator i = std::unique( c.begin(), c.end() );
    c.resize( std::distance(c.begin(), i) );
    // Add 'M' (or MARK, if we were using strings).
    c.push_back( 'M' );
    // Add all the elements excluding 'M' to the back of the list.
    std::copy( ++c.rbegin(), c.rend(), std::back_inserter(c) );
    return 0;
}

如果某些元素不重复，您还没有给出期望的输出。因此，我无法为这种情况提供正确的行为。该方法可以通过使用std::unordered_set (c++ 11)或其他散列集(例如Dinkum的stdext::hash_set)来实现O(n)。