版權(quán)聲明：本文為博主原創(chuàng)文章邻辉，未經(jīng)博主允許不得轉(zhuǎn)載骏啰。
難度：容易
要求：
給定一個(gè)單鏈表和數(shù)值x磅叛，劃分鏈表使得所有小于x的節(jié)點(diǎn)排在大于等于x的節(jié)點(diǎn)之前。你應(yīng)該保留兩部分內(nèi)鏈表節(jié)點(diǎn)原有的相對順序皆辽。
樣例
給定鏈表 1->4->3->2->5->2->null柑蛇，并且 x=3返回** 1->2->2->4->3->5->null**
思路：
多指針偏移
/**
* @param head: The first node of linked list.
* @param x: an integer
* @return: a ListNode
*/
public ListNode partition(ListNode head, int x) {
if(head == null){
return null;
}
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
dummy.next = head;
ListNode target = null;
ListNode tmp = null;
while(prev.next != null){
if(target == null){
if(x <= prev.next.val){
target = prev.next;
tmp = prev.next;
}else{
prev = prev.next;
}
}else{
if(tmp.next == null){
break;
}
if(tmp.next.val < x){
prev.next = tmp.next;
prev = prev.next;
tmp.next = tmp.next.next;
}else{
tmp = tmp.next;
}
}
}
if(target != null){
prev.next = target;
}
return dummy.next;
}
思路：
分2個(gè)鏈表,這樣思路比較清晰
public ListNode partition(ListNode head, int x) {
if (head == null) {
return null;
}
ListNode leftDummy = new ListNode(0);
ListNode rightDummy = new ListNode(0);
ListNode left = leftDummy;
ListNode right = rightDummy;
while (head != null) {
if (head.val < x) {
left.next = head;
left = head;
} else {
right.next = head;
right = head;
}
head = head.next;
}
right.next = null;
left.next = rightDummy.next;
return leftDummy.next;
}
