本文共 895 字，大约阅读时间需要 2 分钟。

对于一个链表，我们需要用一个特定阈值完成对它的分化，使得小于等于这个值的结点移到前面，大于该值的结点在后面，同时保证两类结点内部的位置关系不变。

思路：

采用双指针思想，维护node1指针作为前面的插入指针，node2作为后面的删除指针。此时分为两种情况：

• 若链表首节点值大于或等于给定值，首先找到其后第一个小于给定值的节点删除并插入到 node2 之前作为头节点，并令 node1 指向它，然后将 node2 指向原删除节点的下一个节点
• 若链表首节点值小于给定值，那么首先找到从左往右第一个大于或等于给定值的节点 node2，并令 node1 指向其前一个节点

这样从 node2 开始依次向后遍历，每次找到一个小于给定值的节点，就将其删除并插入到 node1 指向节点之后，然后令 node1 指针右移一位，直到 node2 指向NULL

//思路：一拆为二然后合并function partition(head, x) {    //node1记录当前最新的小于x的值，node2记录当前最新的大于等于x的值    let node1 = new ListNode(0), node2 = new ListNode(0);    //cur1指向表头，cur2指向第一个大于等于x的值得位置    let cur1 = node1, cur2 = node2;    while (head != null) {        if (head.val < x) {            node1.next = head;            node1 = node1.next;        } else {            node2.next = head;            node2 = node2.next;        }        head = head.next;    }    node1.next = cur2.next;    node2.next = null;  //以null结尾    return cur1.next;}

转载地址：http://jnuvi.baihongyu.com/