首页 > 代码库 > [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,
Given1->4->3->2->5->2and x = 3,
return1->2->2->4->3->5.
题意:给定一个链表和一个值x,将它划分为所有小于x的节点出现在大于或等于x的节点之前。值得注意的是,不要改变相对顺序,对1->4->3->2->5->2而言,给定x=4则返回1->3->2->2->4->5,前半段不应是按递增的顺序,但相对位置不变即可。
思路:找到第一个值不小x的结点和其前驱pre,然后从该结点往后遍历,找到值小于x结点,然后将其依次放在前驱之后,对于前驱pre则不断的向其后继移动。
方法一:初始代码:思想是,找到第一个大于或者等于x的值及其前驱,然后从x开始向后遍历,但是在遍历的过程,需要用到x前驱的信息,所以又重新定义了一个新的变量preCur。
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode *partition(ListNode *head, int x) 12 { 13 if(head==NULL||head->next==NULL) 14 return head; 15 ListNode *nList=new ListNode(0); 16 nList->next=head; 17 ListNode *pre=nList; 18 ListNode *cur=head; 19 20 while(cur) //找到节点及其前驱pre 21 { 22 if(cur->val >=x) 23 break; 24 pre=cur; 25 cur=cur->next; 26 27 } 28 ListNode *preCur=cur; //cur是不停的向后遍历,preCur则是其前行过程中的前驱 2930 31 while(cur) 32 { 33 if(cur->val <x) 34 { 35 ListNode *temp=cur->next; 36 cur->next=pre->next; 37 pre->next=cur; 38 preCur->next=temp; 39 pre=pre->next; 40 cur=temp; 41 } 42 else 43 { 44 preCur=cur; 45 cur=cur->next; 46 } 47 } 48 return nList->next; 49 } 50 };
方法一:改进版。很明显,cur为第一个值不小于x的节点,然后通过其后继的值来作为判断前行或是将小于x的节点放在前面,这样就可以省去变量。
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode *partition(ListNode *head, int x) 12 { 13 ListNode *nList=new ListNode(0); 14 nList->next=head; 15 ListNode *pre=nList; 16 ListNode *cur=head; 17 18 while(pre->next&&pre-next->val < x) 19 pre=pre->next; 20 21 cur=pre; 22 while(cur->next) 23 { 24 if(cur->next->val <x) 25 { 26 ListNode *temp=cur->next; 27 cur->next=temp->next; 28 temp->next=pre->next; 29 pre->next=temp; 30 pre=pre->next; 31 } 32 else 33 { 34 cur=cur->next; 35 } 36 } 37 return nList->next; 38 } 39 };
方法三:可以通过将值小于x的结点全部拿出来组成一个新的链表,然后将这个新的链表插入第一个值不小于x之前即可。来源Grandyang的博客
1 class Solution 2 { 3 public: 4 ListNode *partition(ListNode *head,int x) 5 { 6 if(head==NULL) return head; 7 ListNode *small=new ListNode(-1); 8 ListNode *big=new ListNode(-1); 9 10 big->next=head; 11 ListNode *cur=small,*p=small; 12 while(cur->next) 13 { 14 if(cur->next->val <x) 15 { 16 p->next=cur->next; 17 p=p->next; 18 //小于x的值,不停的移到small中,然后cur重新连接 19 cur->next=cur->next->next; 20 p->next=NULL; //注意要记得给p->next=NULL 21 } 22 else 23 cur=cur->next; 24 } 25 p->next=big->next; //拼接 26 return small->next; 27 } 28 }
[Leetcode] Partition list 划分链表