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;
	}
}