聲明： 本總結(jié)僅為個(gè)人學(xué)習(xí)總結(jié)弹谁，以防止遺忘而作漾稀，不得轉(zhuǎn)載和商用派近。
題目：給定一個(gè)單鏈表和數(shù)值x，劃分鏈表使得所有小于x的節(jié)點(diǎn)排在大于等于x的節(jié)點(diǎn)之前蟀悦。你應(yīng)該保留兩部分內(nèi)鏈表節(jié)點(diǎn)原有的相對(duì)順序媚朦。
樣例：
給定鏈表 1->4->3->2->5->2->null，并且 x=3日戈，返回 1->2->2->4->3->5->null
分析：
分別申請(qǐng)兩個(gè)指針p1和p2,小于x的添加到p1中,大于等于x的添加到p2中;最后,將p2鏈接到p1的末端即可
時(shí)間復(fù)雜度O(N),空間復(fù)雜度O(1)
Java版本的實(shí)現(xiàn)：
public static void partition(Node pHead, int pivotKey){
//兩個(gè)鏈表的頭指針
Node pLeftHead = new Node(0);
Node pRightHead = new Node(0);
//兩個(gè)鏈表的當(dāng)前最后一個(gè)元素
Node left = pLeftHead;
Node right = pRightHead;
Node p = pHead.next;
while (p != null) {
if (p.value < pivotKey) {
left.next = p;
left = p;
}else {
right.next = p;
right = p;
}
p = p.next;
}
//將right鏈接到left尾部
left.next = pRightHead.next;
right.next = null;
//將整理好的鏈表賦值給當(dāng)前鏈表頭部
pHead.next = pLeftHead.next;
}
測試代碼：
int datas[] = {1,4,3,2,5,2};
Node pH = new Node(0);
for(int i = datas.length-1;i>=0;i--){
Node pNode = new Node(datas[i]);
pNode.next = pH.next;
pH.next = pNode;
}
printLinkedList(pH);
partition(pH, 3);
printLinkedList(pH);
結(jié)果：
Linked List: 0->1->4->3->2->5->2->
Linked List: 0->1->2->2->4->3->5->
