[leetcode]Partition List

新博文地址：Partition List

果然出去玩了一个星期回来状态极差。。。。

Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

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

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

 码代码时，脑子都不会动了。。。纯粹靠一步步调试AC的。囧啊，找到待分割点，将分割点后所有的小节点，插入分割点当做后驱，并维护分割位置tail。返回时，有一个坑，比如2，1 （x  = 2），head = 2，将1插入到2前面时，返回head肯定是不对的，要返回分割点seperator->1,2。我特么在说些什么啊。o(╯□╰)o

 

等第二遍刷的时候，再把代码优化一下吧

    public ListNode partition(ListNode head, int x) {
		if (head == null || head.next == null) {
			return head;
		}
		ListNode seperator = new ListNode(0);
		seperator.next = head;
		boolean isSplit = true;
		while (seperator.next != null) {
			if (seperator.next.val >= x) {
				break;
			}
			seperator = seperator.next;
			isSplit = false;
		}
		ListNode tem = seperator;
		ListNode tail = seperator;
		while (tem.next != null) {
			if (tem.next.val < x) {
				ListNode node = tem.next;
				tem.next = node.next;
				node.next = tail.next;
				tail.next = node;
				tail = node;
			}
			if (tem.next != null && tem.next.val < x) {
				continue;
			} else {
				tem = tem.next;
			}
			if (tem == null) {
				break;
			}
		}
		return isSplit ? seperator.next : head;
	}