86.Partition List
===

###### tags: `Medium` `Linked List` `Two Pointers`

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

### 範例

**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]

**Constraints**:

* The number of nodes in the list is in the range `[0, 200]`.
* -100 <= `Node.val` <= 100
* -200 <= `x` <= 200

### 解答
#### C++

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* leftHalf = new ListNode(0);
        ListNode* rightHalf = new ListNode(0);
        ListNode* leftCurr = leftHalf, * rightCurr = rightHalf;

        while (head != nullptr) {
            if (head->val < x) {
                leftCurr->next = new ListNode(head->val);
                leftCurr = leftCurr->next;
            } else {
                rightCurr->next = new ListNode(head->val);
                rightCurr = rightCurr->next;
            }
            head = head->next;
        }
        rightCurr->next = nullptr;
        leftCurr->next = rightHalf->next;
        return leftHalf->next;
    }
};

> [name=Jerry Wu][time=15 Aug 2023]

#### TypeScript

function partition(
  head: ListNode | null, 
  x: number
): ListNode | null {
  const appendNode = (
    list: ListNode | null, 
    current: ListNode | null, 
    node: ListNode
  ) => {
    if (list === null) {
      list = node;
      current = list;
    } else {
      current!.next = node;
      current = current!.next;
    }
    return { list, current };
  };
  let left: ListNode | null = null;
  let leftCurr: ListNode | null = null;
  let right: ListNode | null = null;
  let rightCurr: ListNode | null = null;
  let current: ListNode | null = head;

  while (current !== null) {
    const nextNode = current.next; // 儲存下一個節點的引用
    current.next = null; // 中斷原始鏈接

    if (current.val >= x) {
      // ChatGPT 教的寫法，真酷
      ({ list: right, current: rightCurr } = appendNode(right, rightCurr, current));
    } else {
      ({ list: left, current: leftCurr } = appendNode(left, leftCurr, current));
    }

    current = nextNode; // 繼續遍歷原始串列
  }

  if (leftCurr) {
    leftCurr.next = right;
    return left;
  }

  return right;
}

- 當成陣列，最後再轉 list

在寫單元測試時為了方便寫的 `helper` 剛好也可以拿來解題，我不習慣操作 list 這種寫法對我比較親切，但效能比較爛。

function partition1(
  head: ListNode | null, 
  x: number
): ListNode | null {
  const left: number[] = [];
  const right: number[] = [];
  let current = head;

  while (current !== null) {
    if (current.val < x) {
      left.push(current.val);
    } else {
      right.push(current.val);
    }
    current = current.next;
  }

  const result = [...left, ...right];
  return createList(result);
}

function createList(values: number[]): ListNode | null {
  let head: ListNode | null = null;
  let current: ListNode | null = null;

  values.forEach((val) => {
    if (current) {
      current.next = new ListNode(val);
      current = current.next;
    } else {
      head = new ListNode(val);
      current = head;
    }
  });

  return head;
}

> [name=Sheep][time=Tues, 15 Aug 2023]

#### Javascript

function partition(head) {
  const right = new ListNode();
  const left = new ListNode();
  let rightHead = right;
  let leftHead = left;

  while (head) {
    if (head.val < x) {
      leftHead.next = head;
      leftHead = leftHead.next;
    } else {
      rightHead.next = head;
      rightHead = rightHead.next;
    }

    head = head.next;
  }

  leftHead.next = right.next;
  rightHead.next = null;

  return left.next;
}

> 用js真的不適合寫這類題目...
> [name=Marsgoat][time=Tues, 15 Aug 2023]

#### C#

public class Solution {
    public ListNode Partition(ListNode head, int x) {
        ListNode lessHead = new ListNode();
        ListNode greaterHead = new ListNode();
        ListNode lessNode = lessHead;
        ListNode greaterNode = greaterHead;

        while (head != null) {
            ref ListNode target = ref (head.val < x ? ref lessNode : ref greaterNode);
            target.next = head;
            target = target.next;
            head = head.next;
        }

        greaterNode.next = null;
        lessNode.next = greaterHead.next;
        return lessHead.next;
    }
}

> [name=Jim][time=Aug 16, 2023]
### Reference

[回到題目列表](https://marsgoat.github.io/XNnote/coding/leetcodeEveryDay.html)