将单向链表按某值划分成左边小、中间相等、右边大的形式

【说明】：

　　本文是左程云老师所著的《程序员面试代码指南》第二章中“将单向链表按某值划分成左边小、中间相等、右边大的形式”这一题目的C++复现。

　　本文只包含问题描述、C++代码的实现以及简单的思路，不包含解析说明，具体的问题解析请参考原书。

　　感谢左程云老师的支持。

【题目】：

　　给定一个单向链表的头节点 head，节点的值类型为整形，再给定一个整数 pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot 的节点，中间部分都是值等于 pivot 的节点，右部分都是值大于 pivot 的节点。除这个要求外，对调整后的节点顺序没有更多的要求。

　　例如：链表 9->0->4->5->1，pivot=3

　　调整后链表可以是 1->0->4->9->5，也可以是 0->1->9->5->4。总之，满足左部分都是小于 3 的节点，中间部分都是等于 3 的节点（本例中这个部分为空），右部分都是大于 3 的节点即可。对某部分内部的节点顺序不做要求。

【进阶】：

　　在原问题的要求之上再增加如下两个要求：

　　在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左到右的顺序与原链表中节点的先后次序一致。

　　例如：链表9->0->4->5->1，pivot=3。调整后的链表是 0->1->9->4->5。在满足原问题的同时，左部分节点从左到右为 0、1。在原链表中也是先出现 0，后出现 1，中间部分在本例中为空，不再讨论；右部分节点从左到右为9、4、5。在原链表中也是先出现9，然后出现4，最后出现5。

　　如果链表长度为N，时间复杂度请达到 O(N)，额外的空间复杂度请达到 O(1)。

【思路】：

　　普通解法：使用快速排序中的分区方法即可。

　　进阶解法：在原链表中按顺序提出左、中、右三个子链表，再进行组合

【编译环境】：

　　CentOS6.7（x86_64）

　　gcc 4.4.7

【实现】：

　　实现及测试代码：

  1 /*
  2  *文件名：lists_partition.cpp
  3  *作者：
  4  *摘要：用C++实现将单向链表按某值划分成左边小、中间相等、右边大的形式
  5  */
  6 
  7 #include <iostream>
  8 
  9 using namespace std;
 10 
 11 struct Node
 12 {
 13     int value;
 14     Node *next;
 15 };
 16 
 17 //打印链表
 18 void printLists(Node *head)
 19 {
 20     while(NULL != head)
 21     {
 22         cout << head->value << " " ;
 23         head = head->next;
 24     }
 25     cout << endl;
 26 }
 27 
 28 //交换链表中的数据
 29 void swap(Node *a,Node *b)
 30 {
 31     int tmp = a->value;
 32     a->value = b->value;
 33     b->value = tmp;
 34 }
 35 
 36 
 37 //快速排序中的分区方法
 38 void arrPartition(Node *arr,int len,int pivot)
 39 {
 40     int index = 0;
 41     len--;
 42     while(index < len)
 43     {
 44         while(index < len && arr[index].value <= pivot)
 45             index++;
 46         swap(&arr[index],&arr[len]);
 47         while(index < len && arr[len].value >= pivot)
 48             len--;
 49         swap(&arr[index],&arr[len]);    
 50     }
 51 }
 52 
 53 //非进阶算法
 54 Node* listPartition1(Node *head,int pivot)
 55 {
 56     if(NULL == head)
 57         return NULL;
 58     Node *cur = head;
 59     int len = 0;
 60     while(NULL != cur)    //统计链表长度
 61     {
 62         len++;
 63         cur = cur->next;
 64     }
 65     
 66     Node *arr = new Node[len];
 67     cur = head;
 68     for(int i=0;i<len;i++)
 69     {
 70         arr[i] = *cur;
 71         cur = cur->next;
 72     }
 73     arrPartition(arr,len,pivot); //分区
 74     for(int i=1;i<len;i++)
 75     {
 76         arr[i-1].next = &arr[i];
 77         Node *ptr = head;
 78         head = head->next;
 79         delete ptr;
 80     }
 81     arr[len-1].next = NULL;
 82     delete head;
 83     return arr;
 84 }
 85 
 86 //进阶算法
 87 Node *listPartition2(Node *head,int pivot)
 88 {
 89     Node *sH = NULL;    //小头
 90     Node *sT = NULL;    //小尾
 91     Node *eH = NULL;    //相等头
 92     Node *eT = NULL;    //相等尾
 93     Node *bH = NULL;    //大头
 94     Node *bT = NULL;    //大尾
 95 
 96     while(NULL != head)
 97     {
 98         Node *next = head->next;
 99         head->next = NULL;
100 
101         if(head->value < pivot)
102         {
103             if(NULL == sH)
104             {
105                 sH = head;
106                 sT = head;
107             }
108             else
109             {
110                 sT->next = head;
111                 sT = head;
112             }
113         }
114         else if(head->value == pivot)
115         {
116             if(NULL == eH)
117             {
118                 eH = head;
119                 eT = head;
120             }
121             else
122             {
123                 eT->next = head;
124                 eT = head;
125             }    
126         }
127         else
128         {
129             if(NULL == bH)
130             {
131                 bH = head;
132                 bT = head;
133             }
134             else
135             {
136                 bT->next = head;
137                 bT = head;
138             }
139         }
140         head = next;
141     }    
142     if(NULL != sT)    //小段链接相等段
143     {
144         sT->next = eH;
145         eT = (NULL == eT ? sT : eT);
146     }
147 
148     if(NULL != eT)    //中段链接大段
149         eT->next = bH;
150     return NULL != sH ? sH : NULL != eH ? eH : bH;
151 }
152 
153 
154 int main()
155 {
156     int arr[] = {9,0,4,5,1};
157     Node *head1 = NULL;
158     Node *ptr1 = NULL;
159     Node *head2 = NULL;
160     Node *ptr2 = NULL;
161     for(int i=0;i<5;i++)
162     {
163         if(NULL == head1 && NULL ==head2)
164         {
165             head1 = new Node;
166             head1->value = arr[i];
167             head1->next = NULL;
168             ptr1 = head1;
169             
170             head2 = new Node;
171             head2->value = arr[i];
172             head2->next = NULL;
173             ptr2 = head2;
174             continue;
175         }
176         ptr1->next = new Node;
177         ptr1 = ptr1->next;
178         ptr1->value = arr[i];
179         ptr1->next = NULL;
180         
181         ptr2->next = new Node;
182         ptr2 = ptr2->next;
183         ptr2->value = arr[i];
184         ptr2->next = NULL;
185     }
186     cout << "list before partiton: " << endl;
187     printLists(head1);
188     cout << "not ordered partition: " << endl;
189     ptr1 = listPartition1(head1,3);
190     printLists(ptr1);
191     
192     cout << "list before partiton: " << endl;
193     printLists(head2);
194     cout << "ordered partition: " << endl;
195     ptr2 = listPartition2(head2,3);
196     printLists(ptr2);
197     return 0;
198 }

View Code

【说明】：

　　关于利用快速排序中的分区方法时，我并未按照左老师所写的代码重写一遍，但是原理是一致的，有兴趣的同学可以参考原书。
　　测试代码较为繁琐，大家凑合着看，因为我用C++重写此题时，使用了delete，所以为了测试两个算法，做了两个相同的链表。

注：

　　转载请注明出处；

　　转载请注明源思路来自于左程云老师的《程序员代码面试指南》。