题解 | #链表分割#

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode head_s = null;//小的头节点
        ListNode head_b = null;//大的头节点
        ListNode small = null;//小于
        ListNode big = null;//大于等于
        ListNode tmp = pHead;//用这个来遍历pHead
        while (tmp != null) {
            if (tmp.val < x) {
                if (small == null) {
                    small = new ListNode(tmp.val);
                    head_s = small;
                } else {
                    small.next = new ListNode(tmp.val);
                    small = small.next;
                }
            } else {
                if (big == null) {
                    big = new ListNode(tmp.val);
                    head_b = big;
                } else {
                    big.next = new ListNode(tmp.val);
                    big = big.next;
                }
            }
            tmp = tmp.next;
        }
        if (small != null) {
            small.next = head_b;
            return head_s;
        } else
            return head_b;
    }
}