链表的分化

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

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

思路:

在遍历链表的过程中,对链表进行拆分,分为小于等于val的链表list1和大于val的链表list2.这里采用哨兵节点代表两个链表的头结点,省却很多判断.
特别要注意的是,要将list2尾节点的next域置为null,避免出现环.例如{1,4,2},3.拆分为两个链表后是1->2和4->2.合并之后会变成1->2<=>4,2和4成环.

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 guard = new ListNode(0);
        guard.next = head;
        ListNode runner = guard;

        ListNode guard2 = new ListNode(0);
        ListNode runner2 = guard2;

        while (runner.next != null) {
            if (runner.next.val > val) {
                runner2.next = runner.next;
                runner2 = runner2.next;
                runner.next = runner.next.next;            
            } else {
                runner = runner.next;
            }
        }
        runner2.next=null;    //一定要将大链表的尾节点的next置为null
        runner.next = guard2.next;
        return guard.next;
       
    }
}