LeetCode 86.Partition List
已知链表头节点指针head与数值X,将所有小于x的节点放在大于或等于x的节点前，且保持这些节点的原来的相对位置
算法：巧用两个临时头节点
class Solution{
public:
ListNode *partition(ListNode *head,int x){
ListNode less_head(0);
ListNode more_head(0);
ListNode *less_ptr = & less_head;
ListNode *more_ptr = & more_head;//对应指针指向这两个头节点
while(head){
if(head->val < x){
less_ptr->next = head;
less_ptr = less_ptr->next;
}
else{
more_ptr->next = head;
more_ptr = more_ptr->next;
}
head = head->next;//遍历链表
}
less_ptr->next =more_head.next;
more_ptr->next = NULL;
return less_head.next;//less_head的next节点即为新链表头节点，返回
}
}
测试
int main(){
ListNode a(1);
ListNode b(4);
ListNode c(3);
ListNode d(2);
ListNode e(5);
ListNode f(2);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
Solution solve;
ListNode *head =solve.partition(&a,3);
while(head){
printf("%d\n,head->val");
head = head->next ;
}
}
