题目描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。（题目来源）

思路

创建两个链表，遍历一遍传入的链表，将值大于x的结点和值小于x的结点依次尾插到两个链表中，最后再将这两个链表链接起来，并返回第一个结点的位置即可。

1.把小于x的结点尾插到less链表，把大于x的结点尾插到greater链表。

2.将less链表与greater链表链接起来。

注意：
1.链接后的链表的最后一个结点的指针域需要置空，否则可能造成链表成环。
2.返回的头指针应是lessHead->next，而不是lessHead。

代码实现

struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

class Partition {
public:
	ListNode* partition(ListNode* pHead, int x) {
		ListNode* greaterHead, *greaterTail, *lessHead, *lessTail;
		//申请一个头结点，后面链接大于x的结点
		greaterHead = greaterTail = (ListNode*)malloc(sizeof(struct ListNode));
		//申请一个头结点，后面链接小于x的结点
		lessHead = lessTail = (ListNode*)malloc(sizeof(struct ListNode));
		greaterTail->next = NULL;//尾指针的指针域置空
		lessTail->next = NULL;//尾指针的指针域置空
		ListNode* cur = pHead;//接收传入的链表，准备遍历
		while (cur)
		{
			if (cur->val < x)
			{
				//结点值小于x，链接到less链表后面
				lessTail->next = cur;
				lessTail = lessTail->next;
			}
			else
			{
				//结点值大于x，链接到greater链表后面
				greaterTail->next = cur;
				greaterTail = greaterTail->next;
			}
			cur = cur->next;//指针后移，遍历后面的结点
		}
		//将less链表和greater链表链接起来
		lessTail->next = greaterHead->next;//greater链表的第一个结点链接到less链表的尾上
		greaterTail->next = NULL;//将greater链表最后一个结点的指针域置空
		ListNode* head = lessHead->next;//接收链接后链表的第一个结点地址
		free(greaterHead);//释放greater链表的头结点
		free(lessHead);//释放less链表的头结点
		return head;//返回新链表
	}
};