花花酱 LeetCode 86. 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.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

Solution: Two dummy heads

Time complexity: O(n)
Space complexity: O(1)

// Author: Huahua

class Solution {

public:

ListNode* partition(ListNode* head, int x) {

ListNode dl(0);

ListNode dr(0);

ListNode* l = &dl;

ListNode* r = &dr;

while (head) {

ListNode*& h = (head->val < x) ? l : r;

h = h->next = head;

head = head->next;

}

r->next = nullptr; // important, to avoid loop

l->next = dr.next;

return dl.next;

}

};

请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物（任意商品）来支持我们

Paypal

Venmo
huahualeetcode

微信打赏