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
Given
1->4->3->2->5->2->null
and x = 3,return
1->2->2->4->3->5->null
.
依旧是基础题,出错的地方是第二个指针next要设为0,错在这里了。。。dummy node的题目
/** * 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 dummyA(0); ListNode dummyB(0); ListNode* a= &dummyA; ListNode* b= &dummyB; while(head){ if (head->val<x){ a->next=head; a=a->next; } else{ b->next=head; b=b->next; } head=head->next; } b->next=NULL; a->next=dummyB.next; return dummyA.next; } };
No comments:
Post a Comment