首页 > 代码库 > Partition List

Partition List

2024-07-18 20:04:06   226人阅读

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，则将其插到小于x部分的链表的尾部；否则，将其插入到不小于x部分的链表的尾部。

 1 class Solution { 2 public: 3     ListNode *partition( ListNode *head, int x ) { 4         if( !head || !head->next ) { return head; } 5         ListNode *prev = 0, *post = head; 6         while( post && post->val < x ) { 7             prev = post; 8             post = post->next; 9         }10         while( post && post->next ) {11             if( post->next->val < x ) {12                 ListNode *tmp = post->next;13                 post->next = tmp->next;14                 if( prev ) {15                     tmp->next = prev->next;16                     prev->next = tmp;17                     prev = tmp;18                 } else {19                     tmp->next = head;20                     head = prev = tmp;21                 }22             } else {23                 post = post->next;24             }25         }26         return head;27     }28 };

 


联系
我们