LeetCode-中等-86-分隔链表-双指针/滑动窗口(C)

原本看上了一题回溯算法的基础题，但因为种种原因还是选择了数据结构的题，还用到了双指针，不错。

题目

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当 保留 两个分区中每个节点的初始相对位置。

示例 1：

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：

输入：head = [2,1], x = 2
输出：[1,2]
 

提示：

链表中节点的数目在范围 [0, 200] 内
-100 <= Node.val <= 100
-200 <= x <= 200

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 用双指针来实现，准确来说，是三指针，更像滑动窗口：
  • 三个指针分别为left，mid，right，均向右移动。
  • left停下：
    • 从left开始往后移动
    • 停下的位置的后一个node值>=x
  • mid停下：
    • 从left->next开始往后移动
    • 停下的位置的后一个node值
  • right停下：
    • 从mid->开始往后移动
    • 停下的位置的后一个node值>=x或为空。
  • 基于这三个指针，每次的移动，都可以将链表分成四部分：
    • (head, left)都是小于x的，
    • (left, mid)都是大于等于x的，
    • (mid, right)都是小于x的，
    • (right, tail)是未排序，但以大于等于x的值开头。
  • 只要把第二个部分与第三个部分交换即可。
  • 在实现中，考虑好第四个部分的情况即可。
• 我的代码框架是按这个来的，
  • 有的地方虽然效率高，却很难看懂，所以做了一点负优化。
  • 以及对于头结点是否小于x的情况，也做了区分处理，因为交换的方式需要我处理。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode *left, *mid, *right, *temp1, *temp2;
    int headLarger = 0;
    left = mid = right =head;
    while(true){

        if(!left) break;
        while(left  &&  left->val < x  &&  left->next  &&  left->next->val < x){
            if(left->next) left = left->next;
        }

        if(left && left->val < x) mid = left->next;
        while(mid  &&  mid->val >= x  &&  mid->next  &&  mid->next->val >= x){
            if(mid->next) mid = mid->next;
        }
        if(!mid) break;

        right = mid->next;  //这里虽然产生了不少计算量，但是让代码更简洁，不用加太多特殊处理。
        while(right  &&  right->val < x  &&  right->next  &&  right->next->val < x){
            right = right->next;
        }

        if(!right) break;
        else if(left  &&  left->val >= x ){
            temp1 = head;
            head = mid->next;
            mid->next = right->next;
            right->next = temp1;
        }
        else{
            temp1 = mid->next;
            temp2 = left->next;
            mid->next = right->next;
            left->next = temp1;
            right->next = temp2;
        }
        temp1 = left;
        left = right;
        right = temp1;
        if( !(left->next && mid->next && right->next) ) break;

    }
    return head;
}