链表分割（解题报告）

  编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前

  给定一个链表的头指针 ListNode* pHead，请返回重新排列后的链表的头指针。注意：分割以后保持原来的数据顺序不变。

  解题思路：用两个链表保存，一个大于等于x的链表，另一个是小于x的链表。最后合并两个链表即可。

                    注意分支的保存。

package link;
public class Partition {
public static void main(String [] args){
ListNode pHead=new ListNode(6);
pHead.next=new ListNode(2);
pHead.next.next=new ListNode(8);
pHead=partition(pHead,2);
while(pHead!=null){
System.out.println(pHead.val);
pHead=pHead.next;
}
}
public static ListNode partition(ListNode pHead, int x) {
ListNode large=null;
ListNode largetail=null;
ListNode small=null;
ListNode smalltail=null;
ListNode current=pHead;
while(current!=null){
if(current.val>=x){
if(large==null){
large=current;
largetail=current;
}
else{
largetail.next=current;
largetail=current;
}
}
else {
if(small==null){
small=current;
smalltail=current;
}
else{
smalltail.next=current;
smalltail=current;
}
}
current=current.next;
}
if(small==null){
current=large;
largetail.next=null;
}
else{
current=small;
smalltail.next=large;
if(large!=null){
largetail.next=null;
}
}
return current;
}
}
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}