/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        if(head==NULL || head->next==NULL )
            return false;
        while(fast!=NULL && fast->next!=NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
                return true;
        }
        return false;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* p = head;
        vector<int> stack;
        int size_ = 0;
        while(p)
        {
            stack.push_back(p->val);
            p=p->next;
            size_++;
        }
        int i = 0;
        p=head;
        while(i<size_)
        {
            if(p->val == stack.back())
            {
                stack.pop_back();
                p = p->next;
                i++;
            }
            else
            {
                return false;
            }
        }

        return true;

    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // l1 = [1,2,4]
        // l2 = [1,3,4]

        ListNode* res = new ListNode(0); // dummy
        ListNode* r = res;

        while(l1 || l2)
        {
            while(l1&&(!l2 || l1->val <= l2->val))
            {
                r->next = new ListNode(l1->val);
                r = r->next;
                l1 = l1->next;
                // 만약 next가 더 없으면 종료 혹은 l2 밸류가 더 작으면 종료.
            }
            while(l2&&(!l1 || l2->val <= l1->val))
            {
                r->next = new ListNode(l2->val);
                r = r->next;
                l2 = l2->next;
            }
        }

        return res->next;


    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* L1 = l1;
        ListNode* L2 = l2;
        ListNode* Merged_List = new ListNode;
        ListNode* head = Merged_List;
        while(L1 || L2)
        {
            while(L1 &&(!L2 || L1->val <= L2->val) )
            {
                Merged_List->next = new ListNode(L1->val); // next에 노드를 추가할떄 항상 생성해야한다. 놓치지 말것
                Merged_List = Merged_List->next;
                L1=L1->next;
            }
            while(L2 && (!L1 || L2->val <= L1->val))
            {
                Merged_List->next = new ListNode(L2->val);
                Merged_List = Merged_List->next;
                L2 = L2->next;
            }
        }
        return head->next;

    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p = head;
        vector<int> stack;
        int size_=0;
        while(p)
        {
            stack.push_back(p->val);
            size_++;
            p=p->next;
        }
        int i = 0;
        ListNode* q = head;
        while(i<size_)
        {
            cout<<stack.back()<<" ";
            q->val = stack.back();
            stack.pop_back();
            q = q->next;
            i++;

        }
        return head;

    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head)
            return nullptr;
        ListNode* p;
        ListNode* t;
        p = head;
        int size_ = 0;
        while(p)
        {
            size_++;
            p=p->next;
        }
        p = head;
        int i = 0;
        do
        {
            p = p->next;
            i++;
        }while(i <size_-n);
        t = p->next;
        *p = *t;
        delete t;
        return head;

    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = head;
        ListNode* q = head;
        int i = 0;
        while(q)
        {
            i++;
            q = q->next;
        }
        int j = 0;
        if(i==n) return head->next;
        while(j<i-n-1)
        {
            p= p->next;
            j++;
        }
        p->next = p->next->next;
        return head;

    }
};