左神算法基础class3—题目12单向链表按某值划分成左边小、中间相等、右边大的形式

普通版：单向链表按某值划分成左边小、中间相等、右边大的形式（不用考虑稳定性且额外空间复杂度为O(n)）

【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数num。实现一个调整链表的函数，将链表调整为左部分都是值小于 num的节点，中间部分都是值等于num的节点，右部分都是值大于num的节点。
例如：链表9->0->4->5->1，num=3。 调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总之，满足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做要求。

1.分析

总体思路是：左边小、中间相等、右边大的形式立马想到荷兰国旗问题（请参考荷兰国旗问题详解），考虑先把链表中的元素放入数组中，再使用荷兰国旗的方法排好序，最后把数组中的元素拷贝回链表中。

2.核心代码

（1）链表的生成及添加元素

①链表结构体定义
数据域，指针域构成

typedef struct ListNode
{
	int val;
	ListNode *next;
}*List;

②生成头节点
注意头节点需指向空

List MakeEmpty()
{
	List head = (List)malloc(sizeof(ListNode));
	head->next = NULL;
	return head;
}

③尾插法

void insert(List head, int num)
{
	//生成新的节点
	List p = (List)malloc(sizeof(ListNode));
	p->val = num;
	p->next = NULL;
	//遍历找到链表最后的位置
	List r = head;
	while(r->next != NULL)
	{
		r = r->next;
	}
	//新节点加入链表，连在末尾处
	r->next = p;	
}

（2）把链表放入数组中

使用vector容器，通过push_back()函数放入数据

vector<int> list_to_arr(List head)
{
	head = head->next;//跳过头节点从第一个数开始	
	vector<int> arr;
	while(head!=NULL)
	{
		arr.push_back(head->val);
		head = head->next;
	}
	return arr;
}

（3）荷兰国旗排序

①用变量x代表小于区域的位置、y代表大于num的区域。刚开始由于不存在小于和大于的区域，则x = -1，y = length,表示指向数组-1、length(都不存在)。再设置变量cur作为遍历的位置，刚开始cur = 0指向数组第一个数。
②.开始遍历
A.如果cur<num ，那么把cur当前的元素和小于区域的下一个数交换，即++x的位置和cur位置的数交换，cur，x后移；
B.如果cur>num，那么把cur当前的元素和大于区域的前一个数交换，即–-y的位置和cur位置的数交换，y前移，cur不变（因为交换过来的数不确定还要再判断）
C.如果cur == num，cur++。
D.如果cur == y结束。

void sort(vector<int> &arr,int num)
{
	int cur = 0;
	int x = -1;
	int y = arr.size();
	while(cur < y)
	{
		if(arr[cur] < num)
		{
			swap(arr[cur++],arr[++x]);
		}
		else if(arr[cur] == num)
		{
			cur++;
		}
		else
		{
			swap(arr[cur],arr[--y]);
		}
	}
}

（4）把数组放回链表中

使用vector容器的迭代器，遍历容器依次放入（或者使用for循环，这里只是想用下迭代器，好久没用了）

void arr_to_list(vector<int>arr,List head)
{
	List cur = head->next;
	vector<int>::iterator beg = arr.begin();
	vector<int>::iterator end = arr.end();
	while(beg != end)
	{
		cur->val = (*beg++);
		cur = cur->next;
	}
}

3.完整代码

#include<iostream>
#include<vector>
using namespace std;

typedef struct ListNode
{
	int val;
	ListNode *next;
}*List;

void arr_to_list(vector<int>arr,List head)
{
	List cur = head->next;
	vector<int>::iterator beg = arr.begin();
	vector<int>::iterator end = arr.end();
	while(beg != end)
	{
		cur->val = (*beg++);
		cur = cur->next;
	}
}

vector<int> list_to_arr(List head)
{
	head = head->next;//跳过头节点从第一个数开始
	vector<int> arr;
	while(head!=NULL)
	{
		arr.push_back(head->val);
		head = head->next;
	}
	return arr;
}

void insert(List head, int num)
{
	//生成新的节点
	List p = (List)malloc(sizeof(ListNode));
	p->val = num;
	p->next = NULL;
	//遍历找到链表最后的位置
	List r = head;
	while(r->next != NULL)
	{
		r = r->next;
	}
	//新节点加入链表，连在末尾处
	r->next = p;	
}

List MakeEmpty()
{
	List head = (List)malloc(sizeof(ListNode));
	head->next = NULL;
	return head;
}

void sort(vector<int> &arr,int num)
{
	int cur = 0;
	int x = -1;
	int y = arr.size();
	while(cur < y)
	{
		if(arr[cur] < num)
		{
			swap(arr[cur++],arr[++x]);
		}
		else if(arr[cur] == num)
		{
			cur++;
		}
		else
		{
			swap(arr[cur],arr[--y]);
		}
	}
}

int main()
{
	//初始化
	List head = MakeEmpty();
	insert(head,9);
	insert(head,0);
	insert(head,4);
	insert(head,5);
	insert(head,1);

	vector<int> arr = list_to_arr(head);
	int num = 3;
	sort(arr,num);
	arr_to_list(arr,head);

	system("pause");
	return 0;
}

4.输出结果

输入9 0 4 5 1过程如下
①1 0 4 5 9 放入9
②1 0 4 5 9 放入1
③1 0 4 5 9 放入0
④1 0 5 4 9 放入4
⑤1 0 5 4 9 放入5结束

进阶版：单向链表按某值划分成左边小、中间相等、右边大的形式（考虑稳定性且额外空间复杂度为O(1)）

【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个整数num。实现一个调整链表的函数，将链表调整为左部分都是值小于 num的节点，中间部分都是值等于num的节点，右部分都是值大于num的节点。
在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左到右的顺序与原链表中节点的先后次序一致。 例如：链表9->0->4->5->1，num=3。调整后的链表是0->1->9->4->5。 在满足原问题要求的同时，左部分节点从左到右为0、1。在原链表中也 是先出现0，后出现1；中间部分在本例中为空，不再讨论；右部分节点 从左到右为9、4、5。在原链表中也是先出现9，然后出现4，最后出现5。
如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。

1.分析

要使额外空间复杂度请达到O(1)，就不能用辅助数组，考虑在原链表上进行修改。
如下图所示，定义六个节点变量分别为less,equ,more用来记录小于、等于、大于各部分第一个位置，less_end,more_end,equ_end用来记录最后一个位置。

对链表进行遍历，分别放入各自的区域，后来的数尾插到最后；

最后，连接非空的区域，此处是end->next = more，再返回第一个非空的部分res，结束。

2.核心代码

(1)判断节点区域

遍历当前链表，找到区域后，判断是否是该区域第一个数，如果是记录当前区域第一个节点，如果不是加入到当前区域最后一个节点，再把当前节点设为该区域最后一个节点，不断重复，直到遍历完为止。

	List cur = head->next;
	List less =	NULL;
	List less_end =	NULL;
	List equ = NULL;
	List equ_end = NULL;
	List more = NULL;
	List more_end = NULL;
	List next = NULL;

	while(cur!=NULL)
	{
		next = cur->next;//记录当前节点的下一位置
		//小于
		if(cur->val < num)
		{
			if(less == NULL)			
			{
				less = cur;
			}
			else
			{
				less_end->next = cur;
			}
			less_end = cur;
		}
		//相等
		else if(cur->val == num)
		{
			if(equ == NULL)			
			{
				equ = cur;	
			}
			else
			{
				equ_end->next = cur;
			}
			equ_end = cur;
		}
		else//大于
		{
			if(more == NULL)			
			{
				more = cur;
			}
			else
			{
				more_end->next = cur;
			}
			more_end = cur;
		}
		cur = next;
	}

(2)节点连接

如果小于区域存在则res为less，判断等于区域存在否，如果存在，小于区域最后一个节点指向等于区域第一个节点，等于区域的最后一个节点指向大于区域的第一个节点。如果等于区域不存在小于区域直接连接大于区域。如果小于区域为空，等于区域不为空，则res等于equ，等于区域连接大于区域。等于区域也为空时res为more，返回res结束。

List res = NULL;
	if(less != NULL)
	{
		res = less;
		if(equ != NULL)
		{
			less_end->next = equ;
			equ_end->next = more;
		}	
		else
			less_end->next = more;	
	}
	else
	{
		if(equ != NULL)
		{
			res = equ;
			equ_end->next = more;
		}
		else
			res = more;	
	}
	return res;

3.完整代码

#include<iostream>
#include<vector>
using namespace std;
typedef struct ListNode
{
	int val;
	ListNode *next;
}*List;

List sort(List head,int num)
{
	List cur = head->next;
	
	List less =	NULL;
	List less_end =	NULL;
	List equ = NULL;
	List equ_end = NULL;
	List more = NULL;
	List more_end = NULL;
	List next = NULL;

	//判断节点区域
	while(cur!=NULL)
	{
		next = cur->next;//记录当前节点的下一位置
		//小于
		if(cur->val < num)
		{
			if(less == NULL)			
			{
				less = cur;
			}
			else
			{
				less_end->next = cur;
			}
			less_end = cur;
		}
		//相等
		else if(cur->val == num)
		{
			if(equ == NULL)			
			{
				equ = cur;	
			}
			else
			{
				equ_end->next = cur;
			}
			equ_end = cur;
		}
		else
		{
			if(more == NULL)			
			{
				more = cur;
			}
			else
			{
				more_end->next = cur;
			}
			more_end = cur;
		}
		cur = next;
	}

	//节点连接
	List res = NULL;
	if(less != NULL)
	{
		res = less;
		if(equ != NULL)
		{
			less_end->next = equ;
			equ_end->next = more;
		}	
		else
			less_end->next = more;	
	}
	else
	{
		if(equ != NULL)
		{
			res = equ;
			equ_end->next = more;
		}
		else
			res = more;	
	}
	return res;
}

void insert(List head, int num)
{
	//生成新的节点
	List p = (List)malloc(sizeof(ListNode));
	p->val = num;
	p->next = NULL;
	//遍历找到链表最后的位置
	List r = head;
	while(r->next != NULL)
	{
		r = r->next;
	}
	//新节点加入链表，连在末尾处
	r->next = p;	
}

List MakeEmpty()
{
	List head = (List)malloc(sizeof(ListNode));
	head->next = NULL;
	return head;
}
int main()
{
	//初始化
	List head = MakeEmpty();
	insert(head,9);
	insert(head,0);
	insert(head,4);
	insert(head,5);
	insert(head,1);

	int num = 3;
	head = sort(head,num);

	system("pause");
	return 0;
}

4.输出结果

具体过程分析中已经用图表示，最后输出0,1,9,4,5