3

我想对包含 0、1 或 2 的链表进行排序。现在，这显然是荷兰国旗问题的变体。 http://en.wikipedia.org/wiki/Dutch_national_flag_problem

与链接中给出的相同的算法是：

“让顶部组从数组顶部向下生长，底部组从底部向上生长，并保持中间组刚好在底部上方。算法存储位置就在顶部组下方，就在底部上方，并且在三个索引的中间上方。在每一步中，检查中间上方的元素。如果它属于顶部组，则将其与顶部下方的元素交换。如果它属于底部，则将其与元素交换就在底部上方。如果它在中间，则离开它。更新适当的索引。复杂度是 Θ(n) 移动和检查。

并且为此给出的 C++ 实现是：

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] == low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }

}

我唯一的问题是我们如何像在数组中那样遍历链表？

4

5 回答 5

4

给定链表单元格，标准单链表不允许您向后移动。但是，您可以使用双向链表，其中每个单元格存储一个下一个和一个前一个指针。这将使您可以前后导航列表。

但是，对于您要解决的特定问题，我认为这没有必要。数组算法和链表算法之间的一个主要区别是，在使用链表时，您可以重新排列列表中的单元格以重新排序列表中的元素。因此，您在上面详述的算法（通过更改数组的内容来工作）实际上可能不是链表上最优雅的算法。

如果您确实在使用链表，解决此问题的一种可能方法如下：

  • 创建包含所有 0、1 或 2 值的列表。
  • 从链表中删除所有单元格并将它们分配到等于 0、1 或 2 的元素列表中。
  • 将这三个列表连接在一起。

这不进行内存分配，纯粹通过重新排列链表单元来工作。它仍然在时间 Θ(n) 中运行，这是另一个优点。此外，您可以做到这一点，而不必向后走（即，这适用于单链表）。

我将把完整的实现留给你，但作为一个例子，这里有一个简单的 C++ 代码，用于将链表单元分配到零、一和二列表中：

struct Cell {
    int value;
    Cell* next;
}

/* Pointers to the heads of the three lists. */
Cell* lists[3] = { NULL, NULL, NULL };

/* Distribute the cells across the lists. */
while (list != NULL) {
    /* Cache a pointer to the next cell in the list, since we will be
     * rewiring this linked list.
     */
    Cell* next = list->next;

    /* Prepend this cell to the list it belongs to. */
    list->next = lists[list->value];
    lists[list->value] = list;

    /* Advance to the next cell in the list. */
    list = next;
}

希望这可以帮助！

于 2013-06-20T01:33:41.470 回答
2

正如其他人所说，没有反向链接就无法在链表中“备份”。虽然这不完全是您问题的答案，但可以通过三个队列轻松完成排序，实现具有三个存储桶的存储桶排序。

队列（堆上的副推）的优点是排序是稳定的。也就是说，如果列表节点中有数据（除了 0、1、2 值的键），每个键的这些数据将保持相同的顺序。

这只是数组的规范算法不适用于列表的众多情况之一。

有一种非常巧妙、简单的方法来实现队列：循环链表，其中第一个节点，比如p，是队列的尾部，因此p->next是头部。这样，代码就很简洁了。 

#include <stdio.h>
#include <stdlib.h>

typedef struct node_s { 
  struct node_s *next; 
  int val;
  int data; 
} NODE;

// Add node to tail of queue q and return the new queue.
NODE *enqueue(NODE *q, NODE *node)
{
  if (q) {
    node->next = q->next;
    q->next = node;
  } 
  else node->next = node;
  return node;
}

// Concatenate qa and qb and return the result.
NODE *cat(NODE *qa, NODE *qb)
{
   NODE *head = qa->next;
   qa->next = qb->next;
   qb->next = head;
   return qb;
}

// Sort a list where all values are 0, 1, or 2.
NODE *sort012(NODE *list)
{
  NODE *next = NULL, *q[3] = { NULL, NULL, NULL};

  for (NODE *p = list; p; p = next) {
    next = p->next;
    q[p->val] = enqueue(q[p->val], p);
  }
  NODE *result = cat(q[0], cat(q[1], q[2]));

  // Now transform the circular queue to a simple linked list.
  NODE *head = result->next;
  result->next = NULL;
  return head;
}

int main(void)
{
  NODE *list = NULL;
  int N = 100;

  //  Build a list of nodes for testing
  for (int i = 0; i < N; ++i) {
    NODE *p = malloc(sizeof(NODE));
    p->val = rand() % 3;
    p->data = N - i;  // List ends up with data 1,2,3,..,N
    p->next = list;
    list = p; 
  }
  list = sort012(list);
  for (NODE *p = list; p; p = p->next)
    printf("key val=%d, data=%d\n", p->val, p->data);
  return 0;
}

现在这是一个完整的简单测试，并且运行良好。

这是未经测试的。（如果我有时间，我会尝试测试它。）但它至少应该非常接近解决方案。

于 2013-06-20T02:50:59.237 回答
1

使用双向链表。如果您已经实现了一个链表对象和相关的链表节点对象，并且能够正向遍历它，那么反向遍历并不是一大堆工作。

假设您有一个 Node 对象，有点像：

public class Node
{
    public Node Next;
    public Object Value;
}

然后你真正需要做的就是改变你的 Node 类，然后你将 Insert 方法向上一点以跟踪之前出现的 Node：

public class Node
{
    public Node Next;
    public Node Previous;
    public Object Value;
}

public void Insert(Node currentNode, Node insertedNode)
{
    Node siblingNode = currentNode.Next;

    insertedNode.Previous = currentNode;
    insertedNode.Next = siblingNode;

    if(siblingNode!= null)
        siblingNode.previous = insertedNode;

    currentNode.next = insertedNode;
}

PS 抱歉，我没有注意到包含 C++ 内容的编辑，所以它更像 C#

于 2013-06-20T01:35:05.027 回答
1

通过更改节点而不是节点数据适用于所有情况。希望它永远不会太晚！

METHOD(To throw some light on handling corner cases):
1. Keep three dummy nodes each for 0,1,2;
2. Iterate throught the list and add nodes to respective list.
3. Make the next of zero,one,two pointers as NULL.
4. Backup this last nodes of each list.
5. Now handle 8 different possible cases to join these list and Determine the HEAD.

zero one two
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

这个在 C++ 中的实现。

Node* sortList(Node *head)
{
   struct Node dummyzero,dummyone,dummytwo;
   dummyzero.next = dummyone.next = dummytwo.next = NULL;

   struct Node *zero =&dummyzero,*one = &dummyone,*two=&dummytwo;
   Node *curr = head,*next=NULL;
   while(curr)
   {
       next = curr->next;
       if(curr->data==0)
       {
           zero->next = curr;
           zero = zero->next;
       }
       else if(curr->data==1)
       {
           one->next = curr;
           one = one->next;
       }
       else
       {
           two->next = curr;
           two = two->next;
       }
       curr = next;
   }
   zero->next = one->next = two->next =NULL;                        //Since this dummynode, No segmentation fault here.
   Node *zerolast = zero,*onelast = one,*twolast = two;
   zero = dummyzero.next;
   one = dummyone.next;
   two = dummytwo.next;

   if(zero==NULL)
   {
        if(one==NULL)
            head = two;
        else
        {
            head = one;
            onelast->next = two;
        }
   }
   else
   {
       head = zero;
       if(one==NULL)
           zerolast->next = two;
       else
       {
           zerolast->next = one;
           onelast->next = two;
       }
   }
   return head;
}
于 2017-07-16T11:51:35.963 回答
0

这个想法是使用荷兰国旗排序算法，稍作修改：
按照荷兰国旗方法对 0 和 1 进行排序，
但是对于 2 而不是将它们添加到列表末尾，将它们保存在单独的链表中。
最后将 2 的列表附加到 0 和 1 的排序列表中。

Node * sort012_linked_list(Node * head) {

  if (!head || !head->next)
    return head;

  Node * head_of_2s = NULL;

  Node * prev = NULL;
  Node * curr = head;

  while (curr) {
    if (curr->data == 0) {
      if (prev == NULL || prev->data == 0) {
        prev = curr;
        curr = curr->next;
      }
      else {
        prev->next = curr->next;
        curr->next = head;
        head = curr;
        curr = prev->next;
      }
    }
    else if (curr->data == 1) {
      prev = curr;
      curr = curr->next;
    }
    else { // curr->data == 2
      if (prev == NULL) {
        head = curr->next;
        curr->next = head_of_2s;
        head_of_2s = curr;
        curr = head;
      }
      else {
        prev->next = curr->next;
        curr->next = head_of_2s;
        head_of_2s = curr;
        curr = prev->next;
      }
    }
  }

  if (prev)
    prev->next = head_of_2s;

  return head;
}
于 2015-06-29T19:22:06.753 回答