#include<iostream>
int removeElement(int* nums, int numsSize, int val) {
    int* p = (int*)malloc(sizeof(int) * numsSize);
    int pos = 0;
    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
        if (nums[i] != val)
        {
            p[pos++] = nums[i];
        }
    }
    for (i = 0; i < pos; i++)
    {
        nums[i] = p[i];
    }
    return pos;
}
int removeElement(int* nums, int numsSize, int val) {
    int left1 = 0;
    int left2 = 0;
    while (left1 < numsSize)
    {
        if (nums[left1] != val)
        {
            nums[left2++] = nums[left1++];
        }
        else
        {
            left1++;
        }
    }
    return left2;
}
int removeDuplicates(int* nums, int numsSize) {
    int left1 = 0;
    int left2 = 0;
    while (left1 < numsSize)
    {
        if (nums[left1] != nums[left2])
        {
            nums[++left2] = nums[left1++];
        }
        else
        {
            left1++;
        }
    }
    return left2 + 1;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int end1 = m - 1;
    int end2 = n - 1;
    int end = m + n - 1;
    while (end1 >= 0 && end2 >= 0)
    {
        if (nums2[end2] >= nums1[end1])
        {
            nums1[end] = nums2[end2];
            end--;
            end2--;
        }
        else
        {
            nums1[end] = nums1[end1];
            end--;
            end1--;
        }
    }
    while (end2 >= 0)
    {
        nums1[end--] = nums2[end2--];
    }
}
#include<stdio.h>
struct ListNode {
    int val;
    struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* prev = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        if (cur->val == val)
        {
            if (head->val == val)
            {
                cur = head->next;
                free(head);
                head = cur;
            }
            else
            {
                prev->next = cur->next;
                free(cur);
                cur = prev->next;
            }
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
    return head;
}
struct ListNode* reverseList(struct ListNode* head) {
    //链表为空：
    if (head == NULL)
        return NULL;
    struct ListNode* n1, * n2, * n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
           n3 = n3->next;
    }
    return n1;
}
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* newHead = NULL;
    while (cur)
    {
        struct ListNode* next = cur->next;
        cur->next = newHead;
        newHead = cur;
        cur = next;
    }
    return newHead;
}
struct ListNode* removeElements(struct ListNode* head, int val) {
    struct ListNode* newHead = NULL;
    struct ListNode* tail = NULL;
    struct ListNode* cur = head;
    while (cur)
    {
        if (cur->val != val)
        {
            //尾插
            //赋值第一个节点
            if (tail == NULL)
            {
                newHead = tail = cur;
            }
            //继续后面尾插
            else
            {
                tail->next = cur;
                tail = tail->next;
            }
            cur = cur->next;
        }
        else
        {
            struct ListNode* del = cur;
            cur = cur->next;
            free(del);
        }
    }
    //如果最后一个是=val的节点，free()后，tail不能再指向free()掉的节点
    if (tail)
        tail->next = NULL;
    return newHead;
}
struct ListNode* middleNode(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}
struct ListNode* middleNode(struct ListNode* head) {
    int len = 0;
    struct ListNode* cur = head;
    while (cur)
    {
        cur = cur->next;
        len++;
    }
    len /= 2;
    while (len--)
    {
        head = head->next;
    }
    return head;
}
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
    // write code here
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    while (k--)
    {
        if (fast == NULL)
            return NULL;
        fast = fast->next;
    }
    while (fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* newHead = NULL;
    struct ListNode* tail = NULL;
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    while (cur1 && cur2)
    {
        if (cur1->val <= cur2->val)
        {
            if (tail == NULL)
            {
                tail = newHead = cur1;
            }
            else
            {
                tail->next = cur1;
                tail = tail->next;
            }
            cur1 = cur1->next;
        }
        else
        {
            if (tail == NULL)
            {
                tail = newHead = cur2;
            }
            else
            {
                tail->next = cur2;
                tail = tail->next;
            }
            cur2 = cur2->next;
        }
    }
    while (cur1)
    {
        if (tail == NULL)
        {
            tail = newHead = cur1;
        }
        else
        {
            tail->next = cur1;
            tail = tail->next;
        }
        cur1 = cur1->next;
    }
    while (cur2)
    {
        if (tail == NULL)
        {
            tail = newHead = cur2;
        }
        else
        {
            tail->next = cur2;
            tail = tail->next;
        }
        cur2 = cur2->next;
    }
    return newHead;
}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));
    guard->next = NULL;
    struct ListNode* tail = guard;
    struct ListNode* cur1 = list1;
    struct ListNode* cur2 = list2;
    while (cur1 && cur2)
    {
        if (cur1->val <= cur2->val)
        {
            tail->next = cur1;
            cur1 = cur1->next;
        }
        else
        {
            tail->next = cur2;
            cur2 = cur2->next;
        }
        tail = tail->next;
    }
    if (cur1)
        tail->next = cur1;
    if (cur2)
        tail->next = cur2;
    struct ListNode* head = guard->next;
    free(guard);
    return head;
}
struct ListNode {
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        // write code here
        struct ListNode* lessGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode* grateGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
        lessGuard->next = NULL;
        grateGuard->next = NULL;
        struct ListNode* lessTail = lessGuard;
        struct ListNode* grateTail = grateGuard;
        struct ListNode* cur = pHead;
        //分别尾插到两个带哨兵位的头节点上
        while (cur)
        {
            if (cur->val < x)
            {
                lessTail->next = cur;
                lessTail = lessTail->next;
            }
            else
            {
                grateTail->next = cur;
                grateTail = grateTail->next;
            }
            cur = cur->next;
        }
        //合并两个链表
        lessTail->next = grateGuard->next;
        grateTail->next = NULL;
        struct ListNode* head = lessGuard->next;
        free(lessGuard);
        free(grateGuard);
        return head;
    }
};
class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head) {
        struct ListNode* fast = head;
        struct ListNode* slow = head;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
    struct ListNode* reverseList(struct ListNode* head) {
        struct ListNode* cur = head;
        struct ListNode* newHead = NULL;
        while (cur)
        {
            struct ListNode* next = cur->next;
            cur->next = newHead;
            newHead = cur;
            cur = next;
        }
        return newHead;
    }
    bool chkPalindrome(ListNode* A) {
        // write code here
        //找中间节点：
        struct ListNode* mid = middleNode(A);
        //逆置后半部分：
        struct ListNode* rmid = reverseList(mid);
        //进行比较：
        struct ListNode* cur = A;
        while (cur && rmid)
        {
            if (cur->val != rmid->val)
            {
                return false;
            }
            cur = cur->next;
            rmid = rmid->next;
        }
        return true;
    }
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    //判断链表是否为空：
    if (headA == NULL || headB == NULL)
        return NULL;
    //找尾节点：
    int lenA = 0;
    while (curA->next)
    {
        curA = curA->next;
        lenA++;
    }
    int lenB = 0;
    while (curB->next)
    {
        curB = curB->next;
        lenB++;
    }
    if (curA != curB)
    {
        return NULL;
    }
    //长的先走差距步：
    int gap = abs(lenA - lenB);
    struct ListNode* longList = headA;
    struct ListNode* shortList = headB;
    if (lenA < lenB)
    {
        longList = headB;
        shortList = headA;
    }
    while (gap--)
    {
        longList = longList->next;
    }
    //同时走：
    while (longList != shortList)
    {
        longList = longList->next;
        shortList = shortList->next;
    }
    return longList;
}
bool hasCycle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (fast == slow)
            return true;
    }
    return false;
}