荷兰国旗问题(单链表)

题目

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

例子：

9->0->4->5->1,pivot=3,调整后为1->0->4->9->5

进阶：在原问题的基础上再增加两个要求，左中右三部分都要稳定性，要求时间复杂度为O(N),额外空间复杂度为O(1)。

例子：

9->0->4->5->1,pivot=3,调整后为
0->1->9->5->4

思路

按照常规思路可以划分3个区域，一个smallBoundary,一个largeBoundary,而中间的就是等于的区域了。大小区间左右夹攻，如下图所示：

上面的方法并不具备稳定性，所以这里提供方法二。
因为这是链表,所以我们可以创建三个指针，分别代表大中小的链表头，再完成三个链表后再拼接即可。

下面看下具体实现。

实现

//将单向链表按某值划分成左边小、中间相等、右边大的形式（荷兰国旗问题）
    public static class Node {
        public int value;
        public Node next;

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

    //方法1:放入数组中，用数组的方式解决
    public static Node listPartition1(Node head, int pivot) {
        int i = 0;
        Node temp = head;
        while(temp != null) {
            i++;
            temp = temp.next;
        }
        Node[] container = new Node[i];

        //装进数组中
        for(i = 0; i < container.length; i++) {
            container[i] = head;
            head = head.next;
        }
        int smallBoundary = -1;
        int largeBoundary = container.length;

        i = 0;
        while(i != largeBoundary) {
            if(container[i].value < pivot) {    //小于
                swap(container, ++smallBoundary, i++);
            }else if(container[i].value > pivot) {
                swap(container, --largeBoundary,i); //这里不移动，是因为你无法知晓largeBoundary前一位换来的数是大于还是小于pivot的，需要检查
            }else {
                i++;
            }
        }

        for(i = 0; i < container.length - 1; i++) {
            container[i].next = container[i + 1];
        }

        container[container.length - 1].next = null;
        return container[0];
    }

    //方法2
    public static Node listPartition2(Node head, int pivot) {

        Node smallHead = null;
        Node smallTail = null;
        Node equalHead = null;
        Node equalTail = null;
        Node largeHead = null;
        Node largeTail = null;
        Node nextNode = null;
        //这里需要有一个next节点，保存下一个节点的地址，因为每一个要节点都要抽出来去这三个链表中
        while(head != null) {

            nextNode = head.next;
            head.next = null;
            if(head.value < pivot) {
                if(smallHead == null) {
                    smallHead = head;
                    smallTail = smallHead;
                }else {
                    smallTail.next = head;
                    smallTail = smallHead.next;
                }
            }else if(head.value == pivot) {
                if(equalHead == null) {
                    equalHead = head;
                    equalTail = equalHead;
                }else {
                    equalTail.next = head;
                    equalTail = equalTail.next;
                }
            }else {
                if(largeHead == null) {
                    largeHead = head;
                    largeTail = largeHead;
                }else{
                    largeTail.next = head;
                    largeTail = largeTail.next;
                }
            }
            head = nextNode;
        }

        //拼接
        if(smallHead != null) {
            smallTail.next = equalHead;
            equalTail = equalTail == null ? smallTail : equalTail;
        }
        if(equalTail != null) {
            equalTail.next = largeHead;
        }

        return smallHead != null ? smallHead : equalHead != null ? equalHead : largeHead;
    }


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

    public static void printLinkedList(Node node) {
        System.out.print("Linked List: ");
        while (node != null) {
            System.out.print(node.value + " ");
            node = node.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {
        Node head1 = new Node(7);
        head1.next = new Node(9);
        head1.next.next = new Node(1);
        head1.next.next.next = new Node(8);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(2);
        head1.next.next.next.next.next.next = new Node(5);
        //head1 = listPartition1(head1, 5);
        head1 = listPartition2(head1, 5);
        printLinkedList(head1);

    }