86.分隔链表

链接：86.分隔链表
难度：Medium
标签：链表、双指针
简介：给你一个链表和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。

题解 1 - typescript

• 编辑时间：2021-01-03
• 执行用时：92ms
• 内存消耗：40.5MB
• 编程语言：typescript
• 解法介绍：利用两个节点进行储存。

function partition(head: ListNode | null, x: number): ListNode | null {
  if (head === null) return null;
  const small = new ListNode(0);
  let smallTemp = small;
  const big = new ListNode(0);
  let bigTemp = big;
  let temp: ListNode | null = head;
  while (temp !== null) {
    if (temp.val < x) {
      smallTemp.next = temp;
      smallTemp = smallTemp.next;
    } else {
      bigTemp.next = temp;
      bigTemp = bigTemp.next;
    }
    temp = temp.next;
  }
  smallTemp.next = big.next;
  bigTemp.next = null;
  return small.next;
}

题解 2 - typescript

• 编辑时间：2021-03-14
• 执行用时：100ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：创建新链表进行储存 x 两边的值。

function partition(head: ListNode | null, x: number): ListNode | null {
  if (head === null) return null;
  const big = new ListNode(0);
  let bigP = big;
  const small = new ListNode(0);
  let smallP = small;
  let p: ListNode | null = head;
  while (p !== null) {
    if (p.val >= x) {
      bigP.next = p;
      bigP = p;
      p = p.next;
      bigP.next = null;
    } else {
      smallP.next = p;
      smallP = p;
      p = p.next;
      smallP.next = null;
    }
  }
  smallP.next = big.next;
  return small.next;
}