diff options
| author | crupest <crupest@outlook.com> | 2020-05-18 15:30:58 +0800 |
|---|---|---|
| committer | crupest <crupest@outlook.com> | 2020-05-18 15:30:58 +0800 |
| commit | 4836b87c3dd2f3e6589f14efeef7901320c2e8ce (patch) | |
| tree | 89488aefd8ab35f683e642dc6ff8069b074c6773 /works/solutions/cpp | |
| parent | aa151b2fa24175d0fe695b4a77395ce8265aa0f6 (diff) | |
| download | crupest-4836b87c3dd2f3e6589f14efeef7901320c2e8ce.tar.gz crupest-4836b87c3dd2f3e6589f14efeef7901320c2e8ce.tar.bz2 crupest-4836b87c3dd2f3e6589f14efeef7901320c2e8ce.zip | |
import(solutions): Add problem 86 .
Diffstat (limited to 'works/solutions/cpp')
| -rw-r--r-- | works/solutions/cpp/86.cpp | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/works/solutions/cpp/86.cpp b/works/solutions/cpp/86.cpp new file mode 100644 index 0000000..1f7568c --- /dev/null +++ b/works/solutions/cpp/86.cpp @@ -0,0 +1,80 @@ +/**
+ * Definition for singly-linked list.
+ * struct ListNode {
+ * int val;
+ * ListNode *next;
+ * ListNode(int x) : val(x), next(NULL) {}
+ * };
+ */
+
+struct ListNode
+{
+ int val;
+ ListNode *next;
+ ListNode(int x) : val(x), next(nullptr) {}
+};
+
+class Solution
+{
+public:
+ ListNode *partition(ListNode *head, int x)
+ {
+ if (head == nullptr)
+ return nullptr;
+
+ if (head->next == nullptr)
+ {
+ return head;
+ }
+
+ ListNode less_list_head(0);
+ ListNode greater_list_head(0);
+
+ ListNode *less_list_tail = &less_list_head;
+ ListNode *greater_list_tail = &greater_list_head;
+
+ auto current_head = head;
+ auto prev = head;
+ auto current = head->next;
+ bool less = head->val < x;
+
+ while (current != nullptr)
+ {
+ const bool current_less = (current->val < x);
+ if (less != current_less)
+ {
+ if (less)
+ {
+ less_list_tail->next = current_head;
+ less_list_tail = prev;
+ }
+ else
+ {
+ greater_list_tail->next = current_head;
+ greater_list_tail = prev;
+ }
+
+ less = current_less;
+ current_head = current;
+ }
+ prev = current;
+ current = current->next;
+ }
+
+ if (less)
+ {
+ less_list_tail->next = current_head;
+ less_list_tail = prev;
+ }
+ else
+ {
+ greater_list_tail->next = current_head;
+ greater_list_tail = prev;
+ }
+
+ less_list_tail->next = greater_list_head.next;
+ greater_list_tail->next = nullptr;
+
+ return less_list_head.next;
+ }
+};
\ No newline at end of file |