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;
    }
};

糖逗