86.Partition List

tags: Medium Linked List Two Pointers

86. 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;
    }
};

Jerry Wu15 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;
}

SheepTues, 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真的不適合寫這類題目…
MarsgoatTues, 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;
    }
}

JimAug 16, 2023

Reference

回到題目列表