LeetCode Partition List 按值分段链表 系统分析

Partition List

Given a linked list and a valuex, partition it such that all nodes less thanxcome before nodes greater than or equal tox.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given1->4->3->2->5->2andx= 3,
return1->2->2->4->3->5.

链表都是麻烦的东西。

一定要学会分情况分析。一开始我是想到在原链表直接操作。

后来想想还是觉得新建一个链表存储小值或者大于等于的值，最后合并两个链表，会比较简单。然后到网上查找一下，发现几乎全部是这种做法。

我原来的想法写写如何做的吧。

在原链表操作就是分为三段：

第一段：小值；

第二段：大于等于的值；

第三段：是还没有处理完的值。

但是有3个情况：1 可能开始的时候全部小值， 2 可能开始的时候全部是大值 3 分了三段的情况（神奇的是，这也是我写博客的时候才搞清楚的，突然觉得思路从没有那么清楚过！于是重新修改代码，果然更加简洁了）

当遇到大值的时候我们只需要往前搜索，不需做其他操作

当遇到小值的时候就分三种情况，如上，处理。

突然觉得这样分析就很科学很清晰了。看来科学地系统地分析真的很重要。

我开始用画图，给每个node赋值分情况分析，虽然这个方法也很好，但是总归要上升到科学系统分析更重要。

下面还有有趣的事情就是Java和C++的操作链表的效率问题，基本上差不多的算法，运行效率居然差别那么多，有图有真相：

看到了吧，找了好几个算法对比也如此。我这里的算法最快了48ms，呵呵。运行几次都没超48ms。

ListNode *partition(ListNode *head, int x) 
	{
		if (!head || !head->next)
		{
			return head;
		}
		ListNode *lessP = head;
		ListNode *larEquP = head;
		ListNode *cur = head->next;

		//注意：引发无限循环
		while (cur)
		{
			if (cur->val < x)
			{
				//1全部是小值的时候
				if(larEquP->val < x)
				{
					cur = cur->next;
					lessP = lessP->next;
					larEquP = larEquP->next;
				}
				//2全部是大值的时候
				else if(head->val >= x)
				{
					larEquP ->next = cur->next;
					cur->next = head;
					head = cur;
					cur = larEquP->next;
					lessP = head;
				}
				//3分了三段值的情况 - 插入lessP后面
				else
				{
					larEquP->next = cur->next;
					cur->next = lessP->next;
					lessP->next = cur;
					lessP = cur;
					cur = larEquP->next;	
				}
			}
			//大值不用动
			else if (cur->val >= x)
			{
				larEquP = larEquP->next;
				cur = cur->next;
			}
		}
		return head;
	}

看见链表要活用dummy节点，使得程序可以很简洁。

//2014-2-14 update
	ListNode *partition(ListNode *head, int x) 
	{
		ListNode dum1(0);
		ListNode dum2(0);
		ListNode *p1 = &dum1;
		ListNode *p2 = &dum2;

		while (head)
		{
			if (head->val < x) 
			{
				p1->next = head;
				p1 = p1->next;
			}
			else
			{
				p2->next = head;
				p2 = p2->next;
			}
			head = head->next;
		}
		p1->next = dum2.next;
		p2->next = nullptr; //注意清空结尾之后的数据。
		return dum1.next;
	}