[数据结构与算法]单链表的划分

方法一：额外空间复杂度O(N)，遍历链表，建立节点数组，利用荷兰旗问题中的方法划分数组，如何将数组中的节点成单链表。
方法二：建立三个单链表，分别存储小于、等于大于X的节点。再将三个单链表串一起。法二也可分为两种：
a、初始化六个节点为null。
b、建立三个Node(0)。

package class04P;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

public class Code05P_SmallerEqualBigger {

    public static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt(){
        try{
            st.nextToken();
            return (int)st.nval;
        }catch(Exception e){
            e.printStackTrace();
        }

        return 0;
    }

    public static Node newLinkedList(int len){
        if(len == 0) return null;
        Node head = new Node(nextInt());

        Node cur = head;
        for (int i = 0; i < len - 1; i++) {
            cur.next = new Node(nextInt());
            cur = cur.next;
        }

        return head;
    }

    public static class Node{
        int val;
        Node next;
        public Node(int val){
            this.val = val;
        }
    }

    public static Node smallerEqualBigger1(Node head, int x){

        Node SH = null, ST = null, EH = null, ET = null, BH = null, BT = null;
        while (head != null){
            Node next = head.next;
            head.next = null;//为了让三个链表拼接后，最后结点的next指向null
            if(head.val < x){
                if(ST == null){
                    SH = head;
                    ST = head;
                }else{
                    ST.next = head;
                    ST = head;
                }
            }else if(head.val == x){
                if(EH == null){
                    EH = head;
                    ET = head;
                }else{
                    ET.next = head;
                    ET = head;
                }
            }else{
                if(BT == null){
                    BH = head;
                    BT = head;
                }else{
                    BT.next = head;
                    BT = head;
                }
            }

            head = next;
        }

        if(SH == null){
            if(ET != null){
                ET.next = BH;
                SH = EH;
            }else{
                SH = BH;
            }
        }else{
            if(ET != null){
                ST.next = EH;
                ET.next = BH;
            }else{
                ST.next = BH;
            }
        }

        return SH;
    }

    public static Node smallerEqualBigger2(Node head, int x){
        Node n1 = new Node(0);
        Node n2 = new Node(0);
        Node n3 = new Node(0);
        Node tail1 = n1, tail2 = n2, tail3 = n3;

        while (head != null){
            if(head.val < x){
                tail1.next = head;
                tail1 = head;
            }else if(head.val == x){
                tail2.next = head;
                tail2 = head;
            }else{
                tail3.next = head;
                tail3 = head;
            }
            head = head.next;
        }

        tail2.next = n3.next;
        tail1.next = n2.next;
        tail3.next = null;

        return n1.next;
    }

    public static void printLinkedList(Node head){
        while(head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
    public static void main(String[] args) {

        Node head = newLinkedList(7);

        printLinkedList(smallerEqualBigger2(head, 2));
    }

}