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 tox.
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
.
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ #define LN ListNode class Solution { public: ListNode *partition(ListNode *head, int x) { // Start typing your C/C++ solution below // DO NOT write int main() function LN sguard(-1); LN hguard(-1); LN* sTail=&sguard; LN* hTail=&hguard; while(head) { if (head->val<x) { sTail->next=head; sTail=head; } else { hTail->next=head; hTail=head; } head=head->next; } sTail->next=hguard.next; hTail->next=NULL; return sguard.next; } };