LeetCode | 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.

关于链表指针移动的题，都是要十分仔细耐心。

这题就是从前到后遍历，节点q之前的都是小于x的节点，遍历过程中每遇到一个小于x的就剪切并拼接到q的next位置。

如果被剪切节点本身就和q相连，就不需要剪切了，加个哨兵也能稍微简化代码。

代码

public class PartitionList {
	public ListNode partition(ListNode head, int x) {
		ListNode dummy = new ListNode(0);
		dummy.next = head;
		ListNode p = dummy.next;
		ListNode pPre = dummy;
		ListNode q = dummy;
		while (p != null) {
			ListNode next = p.next;
			if (p.val < x) {
				if (q == pPre) {
					pPre = p;
				} else {
					// cut
					pPre.next = next;
					// paste
					p.next = q.next;
					q.next = p;
				}
				q = p;
				p = next;
			} else {
				pPre = p;
				p = next;
			}
		}
		return dummy.next;
	}
}