将单向链表按某值划分成左边小、中间相等、右边大的形式

【题目】 给定一个单向链表的头节点head，节点的值类型是整型，再给定一个
整 数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于 pivot
的节点，中间部分都是值等于pivot的节点，右部分都是值大于 pivot的节点。
除这个要求外，对调整后的节点顺序没有更多的要求。 例如：链表9->0->4->5-
1，pivot=3。 调整后链表可以是1->0->4->9->5，也可以是0->1->9->5->4。总
之，满 足左部分都是小于3的节点，中间部分都是等于3的节点（本例中这个部
分为空），右部分都是大于3的节点即可。对某部分内部的节点顺序不做 要求。

进阶： 在原问题的要求之上再增加如下两个要求。
在左、中、右三个部分的内部也做顺序要求，要求每部分里的节点从左到右的
顺序与原链表中节点的先后次序一致。 例如：链表9->0->4->5->1，pivot=3。
调整后的链表是0->1->9->4->5。 在满足原问题要求的同时，左部分节点从左到
右为0、1。在原链表中也 是先出现0，后出现1；中间部分在本例中为空，不再
讨论；右部分节点 从左到右为9、4、5。在原链表中也是先出现9，然后出现4，
最后出现5。
如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)。

解题思路：

原问题的思路

（1）使用一个辅助数组来存放链表，然后将数组进行“荷兰国旗问题”那样的划分出小于区、大于区和等于区。（不懂的可以去看我那篇荷兰国旗问题的博客，里面有详细解释）
（2）划分好之后，将数组中的值依次拷贝到链表中，就大功告成。

public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            this.value = data;
        }
    }

public static Node listPartition1(Node head, int pivot) {
        if (head == null) {
            return head;
        }
        Node cur = head;
        int i = 0;
        while (cur != null) {
            i++;
            cur = cur.next;
        }
        Node[] nodeArr = new Node[i]; //辅助数组
        cur = head;
        for (i = 0; i != nodeArr.length; i++) { //将链表的值存入数组中
            nodeArr[i] = cur;
            cur = cur.next;
        }
        arrPartition(nodeArr, pivot);
        for (i = 1; i != nodeArr.length; i++) {
            nodeArr[i - 1].next = nodeArr[i];
        }
        nodeArr[i - 1].next = null;
        return nodeArr[0];
    }

public static void arrPartition(Node[] nodeArr, int pivot) {
        int small = -1;
        int big = nodeArr.length;
        int index = 0;
        while (index != big) {
            if (nodeArr[index].value < pivot) {
                swap(nodeArr, ++small, index++);
            } else if (nodeArr[index].value == pivot) {
                index++;
            } else {
                swap(nodeArr, --big, index);
            }
        }
    }

public static void swap(Node[] nodeArr, int a, int b) {
        Node tmp = nodeArr[a];
        nodeArr[a] = nodeArr[b];
        nodeArr[b] = tmp;
    }

进阶问题的思路

因为要求在左、中、右三个部分的内部也做顺序要求，所以我们需要稳定的算法。

想象有三个单独的链表，small、equal和big。相当于小于、等于、大于区，每个链表设置一个头节点和尾节点。
（1）先遍历一遍链表，分别找到第一个小于、等于、大于pivot的节点，将头节点和尾节点同时设置为找到的对应节点。
（2）继续遍历，找到符合要求的节点就把它连到尾节点的下一个节点，因为一开始头节点和尾节点是同一个节点，所以这个操作相当于将下一个节点和头节点连起来了。同时，将尾节点设置为加进来的新节点。
（3）遍历完成之后，把3个链表串起来。具体操作就是将small链表的尾节点的下一个节点指向equal链表的头节点，equal链表的尾节点的下一个节点指向big链表的头节点。

public static Node listPartition2(Node head, int pivot) {
        Node sHead = null; // small head
        Node sTail = null; // small tail
        Node eHead = null; // equal head
        Node eTail = null; // equal tail
        Node bHead = null; // big head
        Node bTail = null; // big tail
        Node next; // save next node
        // every node distributed to three lists
        while (head != null) {
            next = head.next;
            head.next = null;
            if (head.value < pivot) {
                if (sHead == null) {
                    sHead = head;
                    sTail = head;
                } else {
                    sTail.next = head;
                    sTail = head;
                }
            } else if (head.value == pivot) {
                if (eHead == null) {
                    eHead = head;
                    eTail = head;
                } else {
                    eTail.next = head;
                    eTail = head;
                }
            } else {
                if (bHead == null) {
                    bHead = head;
                    bTail = head;
                } else {
                    bTail.next = head;
                    bTail = head;
                }
            }
            head = next;
        }
        // small and equal reconnect
        if (sTail != null) {
            sTail.next = eHead;
            eTail = eTail == null ? sTail : eTail;
        }
        // all reconnect
        if (eTail != null) {
            eTail.next = bHead;
        }
        return sHead != null ? sHead : eHead != null ? eHead : bHead;
    }