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;

最终用时：超过一小时