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
return
Have you met this question in a real interview? Given
1->4->3->2->5->2->null
and x = 3,return
1->2->2->4->3->5->null
.
Yes
Example
Tags Expand Set two dummy head nodes, put nodes into two head by value
Note: Line 40: Don't forget to set the next of last node is NULL
http://www.cnblogs.com/springfor/p/3862392.html
Time: O(n)
Space: O(1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @param x: an integer * @return: a ListNode */ ListNode *partition(ListNode *head, int x) { // write your code here ListNode* head1 = new ListNode(0); ListNode* head2 = new ListNode(0); ListNode* p1 = head1; ListNode* p2 = head2; ListNode* cur = head; while(cur != NULL){ if(cur->val < x){ p1->next = cur; p1 = p1->next; cur = cur->next; } else{ p2->next = cur; p2 = p2->next; cur = cur->next; } } p2->next = NULL; p1->next = head2 ->next; return head1->next; } }; |
Lintcode second :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @param x: an integer * @return: a ListNode */ ListNode *partition(ListNode *head, int x) { // write your code here ListNode *p1, *p2, *p3, *p4; p1 = new ListNode(0); p2 = new ListNode(0); p3 = p1; p4 = p2; while(head){ if(head->val < x) { p1->next = head; p1 = p1->next; } else { p2->next = head; p2 = p2->next; } head = head->next; } p1->next = p4->next; head = p3->next; p2->next = NULL; //Set the end node points to NULL return head; } }; |
没有评论:
发表评论