首页 > 代码库 > leetcode第一刷_Partition List
leetcode第一刷_Partition List
partition是快排的准备工作,被用在其他很多问题上,比如找满足某个条件的数之类的。
在数组中,可以一头一尾的指针依次置换,这样是不能保证源数组中的相对顺序的。链表中就不一样了,没办法拿到尾部的指针,只能从头部往后找,找到第一不满足partition条件的节点,即较大的数,然后再往后找较小数,把较小数的节点移到前面来,因此跟数组的做法还有个区别,链表的partition只有一个指针在做实际的移动,另一个指针一直保存的是插入的位置。
class Solution { public: ListNode *partition(ListNode *head, int x) { if(!head || !head->next) return head; ListNode *left = head, *right = head, *pre1 = NULL, *pre2 = NULL; while(left&&left->val<x){ pre1 = left; left = left->next; } right = left; while(right){ while(right&&right->val>=x){ pre2 = right; right = right->next; } if(right != left&&right){ pre2->next = right->next; if(pre1 == NULL){ right->next = head; head = right; }else{ right->next = pre1->next; pre1->next = right; } pre1 = right; right = pre2->next; } } return head; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。