/**
* 功能：以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的节点之前。
*/
两种方法：直接创建两个链表：一个链表存放小于x的元素，另一个存放大于或等于x的元素。
1、方法一：插入后端
/* * 直接创建两个链表：一个链表存放小于x的元素，另一个存放大于或等于x的元素。 * 然后迭代访问整个链表，将元素插入before或者after链表末尾。一旦抵达链表末端，则表明拆分完毕，最后合并两个链表。 */ public static LinkedListNode partition(LinkedListNode node, int x){ if( node== null) return null; LinkedListNode beforeStart= null; LinkedListNode beforeEnd= null; LinkedListNode afterStart= null; LinkedListNode afterEnd= null; while( node!= null){ LinkedListNode next= node. next; //将链表存储在next中 node. next= null; //将node的next清零表示，只是添加一个节点，而非以该节点为头结点的链表 if( node. data< x){ if( beforeStart== null){ beforeStart= node; beforeEnd= beforeStart; } else{ beforeEnd. next= node; beforeEnd= node; } } else{ if( afterStart== null){ afterStart= node; afterEnd= afterStart; } else{ afterEnd. next= node; afterEnd= node; } } node= next; } if( beforeStart== null) return afterStart; //合并 beforeEnd. next= afterStart; return beforeStart; } 2、方法二：插入前端 /* * 直接创建两个链表：一个链表存放小于x的元素，另一个存放大于或等于x的元素。 * 然后迭代访问整个链表，将元素插入before或者after链表前端！！！一旦抵达链表末端，则表明拆分完毕，最后合并两个链表。 */ public static LinkedListNode partition2(LinkedListNode node, int x){ if( node== null) return null; LinkedListNode beforeStart= null; LinkedListNode afterStart= null; while( node!= null){ LinkedListNode next= node. next; node. next= null; if( node. data< x){ node. next= beforeStart; beforeStart= node; } else{ node. next= afterStart. next; afterStart= node; } } if( beforeStart== null) return afterStart; LinkedListNode head= beforeStart; while( beforeStart. next!= null){ beforeStart= beforeStart. next; } beforeStart. next= afterStart; return head; }
public static ListNode partition(ListNode pHead, int x) {
if(pHead==null || pHead.next==null) //如果为空，或者只有一个节点直接返回 return pHead; ListNode maxHead = new ListNode(1);//定义大于等于的头节点 ListNode minHead = new ListNode(0);//定义小于的头节点 ListNode posMax = maxHead;//定义一个大于等于的链表 指针，指向当前位置 ListNode posMin = minHead;//定义一个小于的链表 指针，指向当前位置 while(pHead!=null) { while(pHead!=null&&pHead.val<x) { posMin.next = pHead; posMin = posMin.next;//指针后移 pHead = pHead.next; posMin.next = null;//断开与下一位的连接 } while(pHead!=null&&pHead.val>=x)//之所以判断为空是为了避免全部为小于x时，执行到这再调用val会报空指针 { posMax.next = pHead; posMax = posMax.next; pHead = pHead.next; posMax.next = null; } } if(minHead.next==null) return maxHead.next; if(maxHead.next!=null) posMin.next = maxHead.next; return minHead.next; } }import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) { //注意这里有构造函数!!
this.val = val;
}
}*/
//思路:扫描两边遍，第一遍接小于x的,第二遍接大于等于x的
public class Partition {
public ListNode partition(ListNode pHead, int x) {
ListNode head = new ListNode(-1); //保留头结点
ListNode p = pHead;
ListNode h = head;
while(pHead != null){
if(pHead.val < x){
h.next = new ListNode(pHead.val); //新建一个节点接在后面
h = h.next;
}
pHead = pHead.next;
}
while(p != null){
if(p.val >= x){
h.next = new ListNode(p.val);
h = h.next;
}
p = p.next;
}
return head.next;
}
}