LeetCode86 分割链表

• 题目
• 思路

题目

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

思路

这个题目，先开始是我的思路错误，虽然我知道这个题目需要设置临时头结点，但是由于审题不清，我最先开始是想设置一个临时的结点tempnode，然后小于x就插入tempnode之前，大于或等于x就插入tempnode之后，但是当我看完相关的视频之后，发现题目的要求并不是这样的，因为题目是要求保持相对位置，而如果像我那样插入就会出现这样的情况：
1->2->2->tempnode->5->3->4
这样的结果就和题目要求的相反，看过正确答案后，不得不承认这个题目非常简单，只需要设置两个头结点，temp_less和temp_more，将小于x的值插入temp_less后面，将大于或者等于x的值插入到temp_more后面，然后将temp_less和temp_more链接起来，并将temp_more的next指针赋值为NULL，最后返回temp_less->next即可。

中间出现时间超过限制的错误，最后发现不断有输出数据跳出来，检查发现，temp_more的指针没有赋值为NULL，故不断循环下去。
另外注意的是链接两个链表时要连接头结点！！！而temp_less和temp_more不在是头结点了。
最终代码如下：

//技巧在于巧用临时头结点
	ListNode less_head(0);
	ListNode more_head(0);
	ListNode* tempnode_less = &less_head;
	ListNode* tempnode_more = &more_head;
	ListNode* result = head;
	//if head is not NULL
	while (head)
	{
		//save head 's next
		ListNode* next = head->next;
 
		if (head->val <x)
		{
			//create less x list node
			tempnode_less->next = head;
			tempnode_less = head;
		}
		else
		{
			//create more x list node
			tempnode_more->next = head;
			tempnode_more = head;
		}
 
		//begin next node
		head = next;
	}
	//connect list node, care of "more_head.next"
	tempnode_less->next = more_head.next;
	tempnode_more->next = NULL;
	return less_head.next;

最终用时：超过一小时