编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或者等于x的结点之前。
分析：使用两个链表，若当前结点小于x，则将其插入第一个链表的尾部；否则，将其插入第二个链表的尾部。最后，将两个链表拼接即可。
1 //struct Node { 2 // Node(): val(0), next(0) {} 3 // Node( int value ): val(value), next(0) {} 4 // int val; 5 // Node *next; 6 //}; 7 8 Node* partition( Node *head, int x ) { 9 Node guard1, guard2; 10 Node *end1 = &guard1, *end2 = &guard2; 11 while( head ) { 12 if( head->val < x ) { 13 end1->next = head; 14 end1 = head; 15 } else { 16 end2->next = head; 17 end2 = head; 18 } 19 head = head->next; 20 } 21 end2->next = 0; 22 end1->next = guard2.next; 23 return guard1.next; 24 }
运行结果
input:
target: 1
result:
input: 2
target: 1
result:2
input: 13 1
target: 1
result:13 1
input: 3 1 3
target: 2
result:1 3 3
input: 1 2 3
target: 2
result:1 2 3
input: 14 54 96 23 45 12 45
target: 23
result:14 12 54 96 23 45 45
input: 14 54 96 23 45 12 45
target: 2
result:14 54 96 23 45 12 45
input: 14 54 96 23 45 12 45
target: 24
result:14 23 12 54 96 45 45