博文中会简要介绍Leetcode P0086题目分析及解题思路。
“Partition List”是一道比较基础的链表题目，思路简洁清晰，时间复杂度是O(n)。
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.
Example:
Input: head = 1->4->3->2->5->2, x = 3 Output: 1->2->2->4->3->5
这道题核心思路是找到值小于x的结点的插入位置，简单来说就是找到pivot即可。剩下的就是基本的链表插入删除。
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
if (head == null)
return head;
ListNode dummy = new ListNode(0, head);
ListNode left = dummy, prev = dummy, right = head;
// 先找到第一个大于等于x的结点的前缀结点
while (left.next != null && left.next.val < x)
left = left.next;
prev = left;
right = left.next;
while (right != null) {
if (right.val >= x) {
prev = right;
right = right.next;
}
else {
prev.next = right.next;
right.next = left.next;
left.next = right;
left = left.next;
right = prev.next;
}
}
return dummy.next;
}
}
以下是C++的题解代码实现。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (head == NULL)
return head;
ListNode *dummy = new ListNode(0, head);
ListNode *left = dummy, *prev = dummy, *right = head;
// 先找到第一个大于等于x的结点的前缀结点
while (left->next != NULL && left->next->val < x)
left = left->next;
prev = left;
right = prev->next;
while (right != NULL) {
if (right->val >= x) {
prev = right;
right = right->next;
}
else {
prev->next = right->next;
right->next = left->next;
left->next = right;
left = left->next;
right = prev->next;
}
}
return dummy->next;
}
};