C++刷LeetCode（面试题 02.04. 分割链表）【链表】【双指针】
题目描述：编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。
示例:
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void swap(ListNode* temp1, ListNode* temp2){
int temp = temp1 -> val;
temp1 -> val = temp2 -> val;
temp2 -> val = temp;
}
ListNode* partition(ListNode* head, int x) {
if(head == NULL)return head;
ListNode* temp1 = head;
ListNode* temp2 = head -> next;
while(temp2 != NULL){
if(temp2 -> val < x){//找到小于x的元素
while(temp1 != temp2 && temp1 -> val < x)temp1 = temp1 -> next;//和>=x元素，并且在temp2之前的交换
swap(temp1, temp2);
}
temp2 = temp2 -> next;
}
return head;
}
}; {:10_324:}
页:
[1]