调整链表为小于等于k的在前，大于k的在后

调整链表为小于等于k的在前，大于k的在后

对于一个链表，我们需要用一个特定阈值完成对它的分化，使得小于等于这个值的结点移到前面，大于该值的结点在后面，同时保证两类结点内部的位置关系不变。

给定一个链表的头结点head，同时给定阈值val，请返回一个链表，使小于等于它的结点在前，大于等于它的在后，保证结点值不重复。

测试样例：
{1,4,2,5},3
{1,2,4,5}

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;
    ListNode(int val) {
        this.val = val;
    }
}*/
public class Divide {
    public ListNode listDivide(ListNode head, int val) {
        ListNode onehead=null;//用来保存小于等于给定值部分的链表的头
        ListNode onetail=null;//用来保存大于给定值部分的链表的尾 ***一定要记得写这个tail，不然每次都要遍历找尾麻烦死
        ListNode twohead=null;//同上，用来保存大于给定值部分的
        ListNode twotail=null;
        ListNode next=null;//这个是用来保存head的next节点的
        while(head!=null){
            next=head.next;//这两步一定要注意，也是最容易出错的地方，我们的目的是依次获取head里面的值放进自己新建的链表中，所以每次都要将head的next清null，　　　　　　　　　　　　　　　　//这样每次的head都是一个纯净的head，这样直接把这个listnode类型的数据结构直接赋值到目的链表的next域就可以了。 还能想到的就是val和next分开赋值，可是他们需要包含于一个完整的listnode里面，所以很麻烦 
            　　　　　　　　　//这个next是要保存下来用来下一轮传进while中的，不然你给head.next赋值为null，这个链表的后边不是就找不到了me　　　　　　　　head.next=null;
            if(head.val<=val){//如果是小于等于的部分
                if(onehead==null){//判断当前的头结点里面是不是空的，
                    onehead=head;//如果当前的头结点是空的，说明这个值是第一个加进来的，要把他设置为头结点
                    onetail=head;//同时只有一个，那么他也是尾节点

                }else{//如果不是第一个进来的
                    onetail.next=head;//这个时候让目前链表的next指向当前
                    onetail=head;//同时让onetail指向新加入的这个尾部
                }                
            }
            if(head.val>val){//同上
                if(twohead==null){
                    twohead=head;
                    twotail=head;
                }else{
                    twotail.next=head;
                    twotail=head;
                }
        }
            head=next;//把刚刚保存在next里面的head的后面的部分，重新传递给head，用于下一轮的while循环
        }
        if(onehead!=null){//判断onehead是否为空（可能链表中的值都大于给定值），
            onetail.next=twohead;//不为空，说明onehead有next域，可以连接，这里不需要考虑twohead的情况，因为即使twohead为null，也不影响onetail指向他
            
        }else{
            onehead=twohead;//如果onehead为空，说明一个元素也没有（因为第一个加入时就设置onehead了），这个时候应该直接返回twohead,但是为了方便同意输出，将他赋值给onehead，
        }
        
        return onehead;
    }
}