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值<x
    • 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;
}

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注