链表划分

链表划分

问题

这个题目说的是，给你一个单链表和一个数字，你要把小于这个数字的节点都移到链表前面，大于等于这个数字的节点都移到链表后面。并且在较小和较大的这两堆节点中，节点之间的相对顺序保持不变。

比如说，给你的单链表是：

0 -> 4 -> 2 -> 1 -> 8 -> 1

给你的数字是 2。小于 2 的节点有 0/1/1 共 3 个，大于等于 2 的节点有 4/2/8 共 3 个。因此重新划分后得到的链表是：

0 -> 1 -> 1 -> 4 -> 2 -> 8

可以看到，较小的那一堆 0/1/1 三个节点保持了在原链表中的相对顺序，较大的那一堆 4/2/8 三个节点也保持了在原链表中的相对顺序。

代码

public class AlgoCasts {

  public class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
      val = x;
    }
  }

  // Time: O(n), Space: O(1)
  public ListNode partitionAndPreserveOrder(ListNode head, int x) {
    if (head == null) return null;
    ListNode smaller = new ListNode(0), greater = new ListNode(0);
    ListNode ps = smaller, pg = greater;
    for (ListNode p = head; p != null; p = p.next) {
      if (p.val < x) {
        ps.next = p;
        ps = ps.next;
      } else {
        pg.next = p;
        pg = pg.next;
      }
    }
    ps.next = greater.next;
    pg.next = null;
    return smaller.next;
  }

}