本文共 2802 字，大约阅读时间需要 9 分钟。

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

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

测试样例：

{1,4,2,5},3

{1,2,4,5}

思路一：将链表元素放到一个数组中，在数组中实现分化，将小于val的值移动到左边，将大于val的值移动到右边，最后再将其串联成为链表即可。类似于荷兰国旗问题，使用了额外的空间复杂度。

思路二：将单链表分化成为3条链表，遍历链表，小于val的结点形成一条链表list1，等于val的结点形成一条链表list2，大于val的结点形成一条链表list3，然后再将list1，list2，list3连接起来返回头结点即可。

{1620,1134,861,563,1},1134对应输出应该为:{1134,861,563,1,1620}你的输出为:{861,563,1,1134,1620}

注意理解清楚题目的意思：即整个链表应该分成2个部分而不是3个部分，对于分界值val，遍历链表，将小于或者等于val的结点组成链表list1，将大于val的结点放到链表list2，于是即使有等于val的结点，塔门依然是分隔开的，而不是全部集中在一起。思路还是一样的，只是对于题目的理解要准确。

这里要注意几个点：关于引用关系的深入理解：

非常关键点①：千万注意这里：list1、list2的最后一个结点都是引用了list,而list是一整条链表，因此list1，list2在需要保留的结点之后还会拖带这list上面的结点，这是不准确的因此必须将list1，list2尾巴后面list链表的值切断。总结：如果新的链表list1需要对原链表摸个结点之后的全部结点进行引用那么就直接将list赋值给新链表即可，如果新链表list1只需要原链表list上面的某几个结点，那么在list1从list上获取到最后一个需要的结点之后就要手动将list1的next置为null，来切断关联。

非常关键点②：当前resultList指向的是head1链表的头结点，要使得head2能够连接到其尾部需要将resultList指针移动到head1尾部。

public class Divide {    	public ListNode listDivide(ListNode head, int val) {        //特殊的输入        if(head==null) return null;        //构造3条链表,每条链表都要记住头结点        ListNode head1=new ListNode(-1);        ListNode head2=new ListNode(-1);        ListNode list1=head1;        ListNode list2=head2;        //对输入的主链表进行遍历        ListNode list=head;        while(list!=null){            if(list.val<=val){                list1.next=list;                list1=list1.next;            }else if(list.val>val){                list2.next=list;                list2=list2.next;            }             list=list.next;        }/*非常关键点①：千万注意这里：list1、list2的最后一个结点都是引用了list,而list是一整条链表，因此list1，list2在需要保留的结点之后还会拖带这list上面的结点，这是不准确的因此必须将list1，list2尾巴后面list链表的值切断。总结：如果新的链表list1需要对原链表摸个结点之后的全部结点进行引用那么就直接将list赋值给新链表即可，如果新链表list1只需要原链表list上面的某几个结点，那么在list1从list上获取到最后一个需要的结点之后就要手动将list1的next置为null，来切断关联。*/        if(list1.next!=null)  list1.next=null;        if(list2.next!=null)  list2.next=null;                /*已经得到list1，list2，list3，将其连接起来即可;注意：只有不为空的才可以被连接;如果直接连接list1，list2，list3，那么要对list1，list2，list3中        某个项为null进行判断，存在很多种情况，十分麻烦；所以解决方案是重新建立一个链表resultList，将不为null的链表连接到resultList即可。*/        ListNode dummy=new ListNode(-1);        ListNode resultList=dummy;        //说明小于链存在，将其连接到resultList上        if(head1.next!=null){        	resultList.next=head1.next;        	//非常关键点②：当前resultList指向的是head1链表的头结点，要使得head2能够连接到其尾部需要将resultList指针移动到head1尾部        	while(head1.next!=null){        		resultList=resultList.next;        		head1=head1.next;        	}        }        //说明等于链存在，将其连接到resultList上        if (head2.next!=null) {        	resultList.next=head2.next;        	while(head2.next!=null){        		resultList=resultList.next;        		head2=head2.next;        	}		}        //说明大于链存在，将其连接到resultList上        return dummy.next;    }}

转载地址：http://dvzin.baihongyu.com/