定值划分单链表

源自CC150一书，原题描述为 定值x将单链表划分为两部分，左侧都小于x，右侧都大于等于x给定链表的头指针，x；返回划分后的头指针
注意：分割后原来数据顺序不变，且不开辟新空间，即不创建新结点

思路：遍历原链表，四指针划分链表，两两指针划分左右侧链表，在相连，即左侧由两个指针划分结点值都小于x，同理右侧都大于等于x
为方便更好观察链表变化打印了前后两个链表，函数返回值还是按要求返回一个头结点
例：
5->6->3->2->1->null， 3为划分
结果为2->1->5->6->3->null
Java代码描述

public class _04定值划分单链表 {
    public static void main(String[] args) {
        int[] arr = {5, 6, 3, 2, 1};
        Node head = new Node(0);
        Node p = head;
        for (int i = 0; i < arr.length; i++) {
            p.next = new Node(arr[i]);
            p = p.next;
        }
        print(head);
        Node p_head = paration(head, 3);
        print(p_head);

    }
    
    private static Node paration(Node head, int x) {
        Node p = head;
        Node rightBegin = null;
        Node rightEnd = null;
        Node leftBegin = null;
        Node leftEnd = null;
        while(p != null) {
            int pdata = p.data;
            if(pdata < x) {
                if(leftEnd == null) {//左侧第一个元素添加
                    leftBegin = p;
                    leftEnd = p;
                }else {
                    leftEnd.next = p;
                    leftEnd = leftEnd.next;//每次指向最尾
                }
            }else {//右侧
                if(rightEnd == null) {
                    rightBegin = p;
                    rightEnd = p;
                }else {
                    rightEnd.next = p;
                    rightEnd = rightEnd.next;
                }
            }
            p = p.next;
        }
        if(leftBegin == null)//没有比目标值小的元素
            return rightBegin;
        
        leftEnd.next = rightBegin;
        rightEnd.next = null;//清尾操作
        
        return leftBegin;
    }

    private static void print(Node head) {
        Node p = head.next;
        while(p != null) {
            System.out.print(p.data + "->");
            p = p.next;
        }
        System.out.println("null");
        
    }

    private static class Node{
        int data;
        Node next;
        
        public Node(int data) {
            super();
            this.data = data;
        }
        
    }

}