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 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.

分析

无

代码

  1. // Partition List
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     ListNode* partition(ListNode* head, int x) {
  6.         ListNode left_dummy(-1); // 头结点
  7.         ListNode right_dummy(-1); // 头结点
  9.         auto left_cur = &left_dummy;
  10.         auto right_cur = &right_dummy;
  12.         for (ListNode *cur = head; cur != nullptr; cur = cur->next) {
  13.             if (cur->val < x) {
  14.                 left_cur->next = cur;
  15.                 left_cur = cur;
  16.             } else {
  17.                 right_cur->next = cur;
  18.                 right_cur = cur;
  19.             }
  20.         }
  22.         left_cur->next = right_dummy.next;
  23.         right_cur->next = nullptr;
  25.         return left_dummy.next;
  26.     }
  27. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/linear-list/linked-list/partition-list.html