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

list_node * list_partition(list_node * head, int pivot)
{
    //////在下面完成代码
    list_node *smallHead = NULL, *smallTail = NULL;
    list_node *equalHead = NULL, *equalTail = NULL;
    list_node *bigHead = NULL, *bigTail = NULL;
    while (head) {
        if (head->val < pivot) {
            if (smallHead == NULL) {
                smallHead = head;
                smallTail = head;
            } else {
                smallTail->next = head;
                smallTail = head;
            }
        } else if (head->val == pivot) {
            if (equalHead == NULL) {
                equalHead = head;
                equalTail = head;
            } else {
                equalTail->next = head;
                equalTail = head;
            }
        } else {
            if (bigHead == NULL) {
                bigHead = head;
                bigTail = head;
            } else {
                bigTail->next = head;
                bigTail = head;
            }
        }
        head = head->next;
    }
    if (smallTail) smallTail->next = NULL;
    if (equalTail) equalTail->next = NULL;
    if (bigTail) bigTail->next = NULL;
    list_node *res;
    if (smallHead == NULL && equalHead == NULL && bigHead == NULL) res = NULL;
    else if (smallHead == NULL && equalHead == NULL) res = bigHead;
    else if (smallHead == NULL && bigHead == NULL) res = equalHead;
    else if (equalHead == NULL && bigHead == NULL) res = smallHead;
    else if (smallHead == NULL) {
        equalTail->next = bigHead;
        res = equalHead;
    } else if (equalTail == NULL) {
        smallTail->next = bigHead;
        res = smallHead;
    } else if (bigTail == NULL) {
        smallTail->next = equalHead;
        res = smallHead;
    } else {
        smallTail->next = equalHead;
        equalTail->next = bigHead;
        res = smallHead;
    }
    head = res;
    while (head) {
        printf("%d ", head->val);
        head = head->next;
    }
    return res;

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int pivot = in.nextInt();
        Node head = new Node(in.nextInt());
        Node cur = head;
        for (int i = 1; i < n; i++) {
            cur.next = new Node(in.nextInt());
            cur = cur.next;
        }
        head = listPartition(head, pivot);
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    public static Node listPartition(Node head, int pivot) {
        Node sH = null;
        Node sT = null;
        Node eH = null;
        Node eT = null;
        Node mH = null;
        Node mT = 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 = head;
                }
            } else if (head.val == pivot) {
                if (eH == null) {
                    eH = head;
                    eT = head;
                } else {
                    eT.next = head;
                    eT = head;
                }
            } else {
                if (mT == null) {
                    mH = head;
                    mT = head;
                } else {
                    mT.next = head;
                    mT = head;
                }
            }
            head = next;
        }
        if (sT != null) {
            sT.next = eH;
            eT = eT == null ? sT : eT;
        }
        if (eT != null) {
            eT.next = mH;
        }
        return sH != null ? sH : (eH != null ? eH : mH);
    }
}
class Node {
    int val;
    Node next;
    Node(int val) {
        this.val = val;
        this.next = null;
    }
}

# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};
#define Node list_node
int pivot;

list_node * input_list(void)
{
    int n, val;
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    scanf("%d%d", &n, &pivot);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}
void insertHead(Node *head, Node* x) {
    if(x==NULL || head==NULL) return;
    Node* last = head->next;
    head->next = x;
    x ->next = last;
}

list_node * list_partition(list_node * head, int pivot)
{
    //////在下面完成代码
    if(head==NULL || head->next ==NULL)return head;
    Node dummy_head;
    list_node *first = head;
    
    list_node lt,gt,eq;
    Node *l = &lt,*g = &gt, *e = &eq;
    lt.next = gt.next = eq.next = NULL;
    while(first) {
         if(first ->val == pivot) {
             e ->next = first,first = first->next,e = e->next,e->next = NULL;
         }else if(first->val > pivot) {
             g ->next = first,first = first->next, g = g->next,g->next = NULL;
         }else {
             l->next = first,l = l->next,first = first->next, l->next = NULL;
         }
    }
     
    e->next = gt.next;
    l->next = eq.next;
    first = lt.next;
    
    while(first) {
        
        printf("%d ", first->val);
        
        first = first->next;
    }
    
    return lt.next;
    
    
    
    
    
    
    
}


int main ()
{
    list_node * head = input_list();
    list_partition(head, pivot);
    return 0;
}

list_node * list_partition(list_node * head, int pivot)
{
    //原理:建立一个新链表,根据比较值，把原链表一个个插入，具体分成三段。
    //小于在前，等于在中，大于在后。并且找到每段的头结点，小于时，第一段头结点在新链表头。
    //等于时，第二段表头在第一段的链尾。大于时，第三段表头在第二段链尾。再对每段进行头插法
    //mid和t用于记录第一段链尾和第二段链尾(也是第二段和第三段的表头)
    
    //p用于遍历旧链表。h,mid,t分别标记新链表三段的表头。lr用于临时指针，标记p的位置方便插入。
    //f1和f2用于下面所说的标记先后顺序和互斥的关系
    //由于都是采用头插法。
    //小于时，第一次插入的节点就是第一段的链尾，第二段的表头和还可能是第三段的表头；
    //等于时，第一次插入的节点就是第二段的链尾，第三段的表头。
    //其中，小于和等于的情况稍微复杂一点，因为小于和等于都会影响第三段表头的位置。这与它们的执行顺序有关。
    //如果小于的情况先于等于的情况插入，那么在小于的情况中，标记第二段表头mid时，还要标记第三段的表头。
    //如果等于的情况先于小于的情况插入，那么在小于的情况中，标记第二段表头mid时，不用标记第三段表头。
    //例如：k=3，先后插入2、9，5。2不光是第二段表头还是第三段表头。结果2-5-9。
    //例如：k=3，先后插入2、9、3、4、3、5第三段的表头先被设置为2，随后被设置3(第三个)。结果2-3(5)-3(3)-5-4-9
    list_node *new_head = new list_node();
    new_head->next = NULL;
    list_node *h,*mid,*t,*p,*lr;
    h = mid = t = new_head;
    p = head;
    int f1 = 1,f2 = 1;
    while(p != NULL){
        if(p->val > pivot){
                lr= p;
                p = p->next;
                lr->next = t->next;
                t->next = lr;
        }

        else if(p->val < pivot){
            if(f1 == 1 && f2 == 1){
                mid = p;
                t = p;
                f2 ++;
            }
            if(f1 == 2 && f2 == 1) {
                mid = p;
                f2++;
            }
            lr = p;
            p = p->next;
            lr->next = h->next;
            h->next = lr;
        }

        else{
            if(f1 == 1){
                t = p;
                f1++;
            }
            lr = p;
            p = p->next;
            lr->next = mid->next;
            mid->next =lr;
        }
    }
    return new_head->next;
}

思路（左神版）：
1.将链表存到数组中
2.利用快排的partion函数调整数组
3.将数组重新连成链表

import java.io.*;

public class Main {
    static int n, k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        k = Integer.parseInt(str[1]);
        Node h = new Node(-1);
        Node p = h;
        String[] s1 = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            p.next = new Node(Integer.parseInt(s1[i]));
            p = p.next;
        }
        h = h.next;//真实头结点
        h = listPartion(h, k);
        while (h != null) {
            bw.write(h.val + " ");
            h = h.next;
        }
        bw.newLine();
        bw.flush();
    }

    private static Node listPartion(Node h, int k) {
        Node cur = h;
        Node[] arr = new Node[n];
        int i = 0;
        //将链表存到数组
        for (i = 0; i != n; i++) {
            arr[i] = cur;
            cur = cur.next;
        }
        //调整数组
        arrPartion(arr, k);
        //重新连成链表
        for (i = 1; i != n; i++) {
            arr[i - 1].next = arr[i];
        }
        arr[i - 1].next = null;
        return arr[0];
    }

    private static void arrPartion(Node[] arr, int k) {
        int small = -1, big = arr.length;
        int index = 0;
        while (index != big) {
            if (arr[index].val < k) {
                swap(arr, ++small, index++);
            } else if (arr[index].val == k) {
                index++;
            } else {
                swap(arr, --big, index);
            }
        }
    }

    private static void swap(Node[] arr, int i, int j) {
        Node tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
class Node {
    int val;
    Node next;

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value +" ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static Node listPartition(Node head, int pivot) {
        Node lessHead = null;
        Node lessTail = null;
        Node equalHead = null;
        Node equalTail = null;
        Node moreHead = null;
        Node moreTail = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = null;
            if(head.value < pivot) {
                if (lessHead == null) {
                    lessHead = head;
                    lessTail = lessHead;
                } else {
                    lessTail.next = head;
                    lessTail = lessTail.next;
                }
            } else if (head.value == pivot) {
                if (equalHead == null) {
                    equalHead = head;
                    equalTail = equalHead;
                } else {
                    equalTail.next = head;
                    equalTail = equalTail.next;
                }
            } else {
                if (moreHead == null) {
                    moreHead = head;
                    moreTail = moreHead;
                } else {
                    moreTail.next = head;
                    moreTail = moreTail.next;
                }
            }
            head = next;
        }
        if (lessHead != null) {
            lessTail.next = equalHead;
            equalTail = equalTail == null ? lessTail : equalTail;
        }
        if (equalTail != null) {
            equalTail.next = moreHead;
        }
        return lessHead != null ? lessHead : equalHead != null ? equalHead : moreHead;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] parameters = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(parameters[0]);
        int pivot = Integer.parseInt(parameters[1]);
        String[] numbers = bufferedReader.readLine().split(" ");
        Node head = listGenerator(n, numbers);
        head = listPartition(head, pivot);
        printList(head);
    }
}