86. Partition List

2019-11-08 01:37:14

字体：大中小

来源：转载

供稿：网友

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.

直接使用二级指针即可，解法如下：

class Solution {public: ListNode* partition(ListNode* head, int x) { ListNode* less = NULL; ListNode** less_pp = &less; ListNode* not_less = NULL; ListNode** not_less_pp = &not_less; while(head != NULL){ if(head->val < x){ *less_pp = head; less_pp = &(head->next); } else{ *not_less_pp = head; not_less_pp = &(head->next); } head = head->next; } if(less != NULL){ *less_pp = not_less; *not_less_pp = NULL; //注意我们需要把not_less分支最后一各节点赋空，负责会死循环 } else less = not_less; return less; }};

上一篇：JQuery选择器

下一篇：二叉搜索树