首页 > 代码库 > [LeetCode 题解]: Partition List
[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.
题意：
给定一个链表以及一个数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; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。