首页 > 代码库 > [LeetCode 题解]: Partition List

[LeetCode 题解]: Partition List

2024-07-15 04:45:42   214人阅读

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.

题意：

给定一个链表以及一个数x。

要求：

将队列中所有小于x的节点放到大于或等于x的节点之前。

思路：

根据题意，很容易想到利用两个链表：

lower按照先后顺序存放小于x的节点；

higher存放大于等于x的节点。

最后合并分割后的链表，按照lower在前，higher在后的顺序。

class Solution {public:    ListNode *partition(ListNode *head, int x) {        if(head==NULL || head->next==NULL) return head;        // divide list into two parts:        // lower part with all nodes whose value is less than x        // higher part with all nodes whose value is more than x        ListNode *lower = new ListNode(-1);         ListNode *higher = new ListNode(-1);        ListNode *ltail = lower;        ListNode *htail = higher;        ListNode *tmp = head;        while(tmp){            if(tmp->val < x){                ltail->next = tmp;                ltail = ltail->next;            }else{                htail->next = tmp;                htail = htail->next;            }            tmp = tmp->next;         }        htail->next=NULL; // set end of a list        ltail->next=higher->next; // append higher part to the tail of lower part        return lower->next;            }};

 


联系
我们