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

这个咋就只能过90%，不知道后台怎么判断结果的？？？

``` java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int pivot = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        Node head = genLinkedListByHead(arr);
        head = partitionOfLinkedList(head, pivot);
        printLinkedList(head);
    }
    
    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }
    
    public static Node genLinkedListByHead(int[] arr) {
        if (arr == null || arr.length < 1) {
            return null;
        }

        Node next = null, node;
        for (int i = arr.length - 1; i >= 0; i--) {
            node = new Node(arr[i]);
            node.next = next;
            next = node;
        }

        return next;
    }
    
    public static void printLinkedList(Node head) {
        StringBuilder sb = new StringBuilder();
        while (head != null) {
            sb.append(head.val).append(" ");
            head = head.next;
        }
        System.out.println(sb.toString());
    }
    
    public static Node partitionOfLinkedList(Node head, int pivot) {
        Node tou = new Node(0);
        Node lt = tou, eq = null, gt = null, nxt, t;

        // 头插法
        while (head != null) {
            nxt = head.next;
            head.next = null;
            if (head.val < pivot) { // 在 lt 与 lt.next 之间插入 head
                t = lt.next;
                lt.next = head;
                head.next = t;
                lt = head; // lt 后移到 head
            } else if (head.val > pivot) { // 头插法，gt 始终执行头部
                head.next = gt;
                gt = head;
            } else {
                if (eq == null) {
                    // eq 为空，需要连接 lt 的尾部
                    lt.next = head;
                    eq = head;
                } else { // 直接尾***r />                     eq.next = head;
                }
            }
            head = nxt;
        }

        if (eq != null) {
            eq.next = gt;
        } else if (tou.next != null) {
            lt.next = gt;
        } else {
            tou.next = gt;
        }

        return tou.next;
    }
}

```

两种解法：

方法一:用链表时老超时，可以看看第二种方式，第一种这里用纯数组解决的。

import java.util.Scanner;

/**
 * 
 * @author minghai
 * @date 2019年9月6日
 */
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int pivot = scan.nextInt();
		
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = scan.nextInt();
		}
		
		arrPartition(arr,pivot);
        for(int a:arr){
            System.out.print(a+" ");
        }
		
	}
	

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

	private static void swap(int[] nodeArr, int i, int j) {
		int temp = nodeArr[i];
		nodeArr[i] = nodeArr[j];
		nodeArr[j] = temp;
	}
}

方法2：还是超时，不过思路很好，可以实现数据的稳定性，代码为 左神《程序员代码面试指南》中此题金阶题的代码，不过在此OJ测试中，超时，可以通过在从控制台输入时，每取到一个值就判断该值与目标值的大小或相等，然后加到对应的 大、中、小链表中，可以减少一次时间一次循环时间。

package ch02_linked;

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int pivot = scan.nextInt();
		Node head = new Node(scan.nextInt());
		Node cur = head;
		while(--n > 0) {
			cur.next = new Node(scan.nextInt());
			cur = cur.next;
		}
		cur = listPartition2(head, pivot);
		while(cur!=null) {
			System.out.print(cur.val+" ");
			cur = cur.next;
		}
	}
	
	public  static Node listPartition2(Node head, int pivot) {
		Node sH = null; 
		Node sT = null;
		Node eH = null;
		Node eT = null;
		Node bH = null;
		Node bT = null;
		Node next = null;
		while(head != null) {
			next = head.next;
			head.next = null;
			if(head.val < pivot) {
				if(sH == null) {
					sH = head;
					sT = head;
				}else {
					sT.next = head;
					sT = sT.next;
				}
			}else if(head.val == pivot) {
				if(eH == null) {
					eH = head;
					eT = head;
				}else {
					eT.next = head;
					eT = eT.next;
				}
			}else {
				if(bH == null) {
					bH = head;
					bT = head;
				}else {
					bT.next = head;
					bT = bT.next;
				}
			}
			head = next;
		}
		
		if(sT != null) {
			sT.next = eH;
			eT = eT == null ? sT : eT;
		}
		if(eT != null) {
			eT.next = bH;
		}
		return sH != null ? sH : eH != null ? eH : bH;
	}
}