今日面試題：

一個很大的2D矩陣，如果某點的值，由它周圍某些點的值決定，例如下一時刻(i,j) 的值取當前時刻它的8鄰點的平均，那么怎么用MapReduce來實現。

快排單鏈表分析

題目：

快排(QuickSort)單向鏈表(Singly Linked List)。

分析：

思路和數據的快速排序一樣，都需要找到一個pivot元素、或者節點。然后將數組或者單向鏈表劃分為兩個部分，然后遞歸分別快排。

針對數組進行快排的時候，交換交換不同位置的數值，在分而治之完成之后，數據就是排序好的。那么單向鏈表是什么樣的情況呢？除了交換節點值之外，是否有其他更好的方法呢？可以修改指針，不進行數值交換。這可以獲取更高的效率。

在修改指針的過程中，會產生新的頭指針以及尾指針，要記錄下來。在partition之后，要將小于pivot的的部分、pivot、以及大于pivot的部分重新串起來成為一個singly linked list。

在partition時，我們用最后的節點作為pivot。當我們掃描鏈表時，如果節點值大于pivot，將節點移到尾部之后；如果節點小于，保持不變。

在遞歸排序時，我們先調用partition將pivot放到正確的為止并返回pivot，然后，遞歸左邊，遞歸右邊，最后在合成一個單鏈表。

C++實現：

struct node *partition(struct node *head, struct node *end,   
                      struct node **newHead, struct node **newEnd) 
{ 
   struct node *pivot = end; 
   struct node *prev = NULL, *cur = head, *tail = pivot; 
 
   while(cur != pivot) 
   { 
       if(cur->data < pivot->data) 
       { 
          if((*newHead) == NULL) 
               (*newHead) = cur; 
           prev = cur;   
           cur = cur->next; 
       } 
       else 
       { 
           if(prev) 
               prev->next = cur->next; 
           structnode *tmp = cur->next; 
           cur->next = NULL; 
           tail->next = cur; 
           tail = cur; 
           cur = tmp; 
       } 
   } 
   if((*newHead) == NULL) 
       (*newHead) = pivot; 
   (*newEnd) = tail; 
  return pivot; 
} 
struct node *quickSortRecur(struct node *head, struct node *end) 
{ 
   if(!head || head == end) 
       return head; 
   node *newHead = NULL, *newEnd = NULL; 
  struct node *pivot = partition(head, end, &newHead, &newEnd); 
   if(newHead != pivot) 
   { 
      struct node *tmp = newHead; 
       while(tmp->next != pivot) 
           tmp = tmp->next; 
       tmp->next = NULL; 
       newHead = quickSortRecur(newHead, tmp); 
       tmp = getTail(newHead); 
       tmp->next =  pivot; 
   } 
   pivot->next = quickSortRecur(pivot->next, newEnd); 
   returnn ewHead; 
} 
void quickSort(struct node **headRef) 
{ 
   (*headRef) = quickSortRecur(*headRef, getTail(*headRef)); 
   return; 
} 

原文鏈接：http://www.ituring.com.cn/article/49307