C++刷LeetCode（面试题 02.04. 分割链表）【链表】【双指针】

糖逗

题目描述：

1. 编写程序以 x 为基准分割链表，使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x，x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可，其不需要被置于左右两部分之间。
   
2. 
   
3. 示例:
   
4. 
   
5. 输入: head = 3->5->8->5->10->2->1, x = 5
   
6. 输出: 3->1->2->10->5->5->8
   
7. 
   
8. 来源：力扣（LeetCode）
   
9. 链接：https://leetcode-cn.com/problems/partition-list-lcci
   
10. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. /**
   
2. * Definition for singly-linked list.
   
3. * struct ListNode {
   
4. *     int val;
   
5. *     ListNode *next;
   
6. *     ListNode(int x) : val(x), next(NULL) {}
   
7. * };
   
8. */
   
9. class Solution {
   
10. public:
    
11.     void swap(ListNode* temp1, ListNode* temp2){
    
12.         int temp = temp1 -> val;
    
13.         temp1 -> val = temp2 -> val;
    
14.         temp2 -> val = temp;
    
15.     }
    
16.     ListNode* partition(ListNode* head, int x) {
    
17.         if(head == NULL)return head;
    
18.         ListNode* temp1 = head;
    
19.         ListNode* temp2 = head -> next;
    
20.         while(temp2 != NULL){
    
21.             if(temp2 -> val < x){//找到小于x的元素
    
22.                 while(temp1 != temp2 && temp1 -> val < x)temp1 = temp1 -> next;//和>=x元素，并且在temp2之前的交换
    
23.                 swap(temp1, temp2);
    
24.             }
    
25.             temp2 = temp2 -> next;
    
26.         }
    
27.         return head;
    
28.     }
    
29. };

复制代码

糖逗