<file_sep>/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * time : 12ms
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(!head){
            return head;
        }
        auto getLenAndLink = [](ListNode* head)->int{
            ListNode* backup = head;
            int ret = 0;
            while(head->next){
                ++ret;
                head = head->next;
            }
            head->next = backup;
            return ret + 1;
        };
        
        //获取链表长度并连接链表为单循环链表
        int len = getLenAndLink(head);
        //获取右移次数
        int rightRotateNum = k%len;
        
        //右移n次等与左移len-n次
        //减1是为了找到新的头指针的前一个
        //找到头指针的前一个后,要将它的next置为nullptr
        for(int i=0;i<((len-1)-rightRotateNum);++i){
            head = head->next;
        }
        
        ListNode* ret = head->next;
        head->next = nullptr;
        
        return ret;
    }
};<file_sep>/**
 * time : 12ms
 */
//https://leetcode-cn.com/problems/container-with-most-water/solution/container-with-most-water-shuang-zhi-zhen-fa-yi-do/
/**
 * 双指针 一头一尾同时向中间靠拢,减小解空间
 * 两个指针指向两块板,每次一个指针向内收缩
 * 收缩的条件为小的那块板收缩
 * 因为容量取决于短板
 * 只有当短板收缩时,容量才可能增大
 * 长板收缩时,容量只会不变或减小
 */
class Solution {
public:
    #define getArea(i,j) (((j)-(i))*(min(height[i],height[j])))
    int maxArea(vector<int>& height) {
        int head = 0;
        int tail = height.size() - 1;
        int maxx = 0;
        
        while(head < tail){
            maxx = max(maxx,getArea(head,tail));
            if(height[head] < height[tail]){
                ++head;
            }
            else{
                --tail;
            }
        }
        
        return maxx;
    }
};<file_sep>/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * time : 8ms
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !(head->next)){
            return head;
        }
        ListNode v(0);
        ListNode* vhead = &v;
        vhead->next = head;
        
        //pre 已经排序好的链表的最后一个元素
        ListNode* pre = vhead;
        //beg 元素相同的链表的第一个元素
        //end 元素相同的链表的最后一个元素
        ListNode* beg = head;
        ListNode* end = head;
        
        while(end){
            //找到最后一个与beg指向的元素相同的元素
            //beg到end为一个链表,里面所有的元素值都相同,链表长度可能为一
            while(end->next && end->val == end->next->val){
                end = end->next;
            }
            
            //当链表长度为一
            if(beg == end){
                //才将pre指针后移
                pre->next = beg;
                beg = beg->next;
                end = beg;
                pre = pre->next;
            }
            //链表长度不为一
            else{
                //不移动pre指针
                pre->next = end->next;
                beg = end->next;
                end = beg;
            }
        }
        
        return vhead->next;
    }
};
<file_sep>/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * time : 8ms
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(!head || !(head->next)){
            return head;
        }
        ListNode* before = new ListNode(0);
        ListNode* after = new ListNode(0);
        
        //备份指针
        ListNode* ret = before;
        ListNode* afterBackup = after;
        while(head){
            if(head->val < x){
                //小于x的节点链接到before链表
                before->next = head;
                before = head;
            }
            else{
                //大于x的节点链接到after链表
                after->next = head;
                after = head;
            }
            //后移head
            head = head->next;
            //并将上一个节点脱离原链表
            before->next = nullptr;
            after->next = nullptr;
        }
        
        //首尾链表相连
        before->next = afterBackup->next;
        return ret->next;
    }
};<file_sep>/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
/**
 * time : 16ms
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode tt(0);
        ListNode* vhead = &tt;
        ListNode* ret = head;
        ListNode* t = nullptr;
        ListNode* last = nullptr;
        bool once = true;
        bool finish = false;
        vhead->next = head;

        ListNode* tail = head;
        ListNode* tailbackup = tail;
        while (tailbackup) {
            //找到k个元素成为链表
            //不足k个会函数返回
            for (int i = 1; i<k; ++i) {
                tail = tail->next ? tail->next : tail;
                if(tail == last){
                    finish = true;
                    break;
                }
                else{
                    last = tail;
                }
            }
            if(finish){
                break;
            }

            //备份tail
            //当局部反转后,tail会被破坏
            tailbackup = tail->next;
            if (once) {
                ret = tail;
                once = false;
            }
            t = vhead->next;
            reverseList(vhead, tail, tail->next, k);
            vhead = t;
            tail = tailbackup;
        }

        return ret;
    }

    //将vhead->next 到 tail的元素反转 局部反转
    //不足k个不会进入函数
    //反转后将nextListHead拼接到反转后的链表
    void reverseList(ListNode* vhead, ListNode* tail, ListNode* nextListHead,int k) {
        //没有元素 一个元素
        if (vhead->next == nullptr || vhead->next == tail) {
            return;
        }

        ListNode* leftListHead = vhead->next;
        int i = 0;
        while (i++ < k && leftListHead != tail->next && leftListHead != nullptr) {
            ListNode* t = vhead->next;
            vhead->next = leftListHead;
            leftListHead = leftListHead->next;
            vhead->next->next = t;

            if (vhead->next->next == vhead->next) {
                vhead->next->next = nextListHead;
            }
        }
    }
};