No. 86 - Partition List
====


---

## [LeetCode 86 -- Partition List](https://leetcode.com/problems/partition-list/)

### 題目描述

Given the head of 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 `x=4` and the linked list as follow

digraph {
                node [shape = circle];
                rankdir=LR
                1->6->2->5->3->4
}

After partition,

digraph {
                node [shape = circle];
                rankdir=LR
                1->2->3->6->5->4
}

Example 1.

Input: head = [1,4,3,2,5,2], x = 3
Output: [1,2,2,4,3,5]

Example 2.

Input: head = [2,1], x = 2
Output: [1,2]

---

### 解法

本題目的是將 linked list 的 nodes 做分類，若是 node 的值若比給定的 `x` 小則將 node 移動到 linked list 前面，並且依照先後順序排列。

這題的解法很簡單，我們只需要建立兩個新的 linked list `before_list` 跟 `after_list` 並依序訪問原本的 linked list 的每個 node，當 node 的值小於 `x` 則屬於 `before_list`，而不小於 `x` 的 node 則屬於 `after_list`。

尋訪 nodes 並判別加入 `before_list` 或 `after_list` 得作法如下:

ListNode *before_head = new ListNode(0);
ListNode *after_head = new ListNode(0);
ListNode *before = before_head;
ListNode *after = after_head;
while (head) {
if (head->val < x) {
  before->next = head;
  before = before->next;
}
else {
  after->next = head;
  after = after->next;
}
head = head->next;
}

我們以下面的 linked list 為例來說明上面程式的結果

digraph {
                node [shape = circle];
                rankdir=LR
                1->6->2->5->4->3
}

我們設 `x=4`，則 `before_list` 跟 `after_list` 會如下面所示

digraph {
                label="before_list"
                node [shape = circle];
                rankdir=LR
                0->1->2->3
}

digraph {
                label="after_list"
                node [shape = circle];
                rankdir=LR
                0->6->5->4->3
}

在尋訪完原本的 linked list 並分類出 `after_list` 跟 `before_list` 後，我們需要把 `after_list` 最後的 node 的下一個指標指向 `NULL` 才行，否則會像上面的 `after_list` 一樣本來應該最後一個 node 是 4 但因為沒有把 node 4 的下一個指標指向 `NULL` 他會接著原本的 linked list 的下一個 node 3。

最後我們再把 `before_list` 最後的 node 的下一個指標指向 `after_list` 的第一個 node 的下一個 node 即可。

完整的程式碼如下面所示:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
      ListNode *before_head = new ListNode(0);
      ListNode *after_head = new ListNode(0);
      ListNode *before = before_head;
      ListNode *after = after_head;
      while (head) {
        if (head->val < x) {
          before->next = head;
          before = before->next;
        }
        else {
          after->next = head;
          after = after->next;
        }
        head = head->next;
      }
      after->next = NULL;
      before->next = after_head->next;
      return before_head->next;
    }
};

### 複雜度分析

由於整個分類的過程需要走訪 linked list 所有的 nodes 所以時間複雜度為 $O(N)$。

至於空間複雜度的部分由於我們只需要宣告常數個 node 指標所以複雜度為 $O(1)$。