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