class MyLinkedList {
public:
    /** 初始化数据结构 */
    MyLinkedList():head(new node()),tail(head),size(0) {}
    
    /** 得到链表中第index个结点的值，index小于0或大于链表长度（链表的index从0开始），返回-1 */
    int get(int index) {
        if(index>=size||index<0)
            return -1;
        else if(index==size-1)
            return tail->val;
        
        node *cur=head->next;
        while(index--)
            cur=cur->next;
        return cur->val;
    }
    
    /** 添加新的头节点 */
    void addAtHead(int val) {
        ++size;
        node *tmp=new node(val);
        tmp->next=head->next;
        head->next=tmp;
        //注意更新尾节点
        if(size==1)
            tail=tmp;
    }
    
    /** 在链表最后添加一个结点. */
    void addAtTail(int val) {
        ++size;
        node *tmp=new node(val);
        tail->next=tmp;
        tail=tmp;
    }
    
    /** 在链表第index个结点前添加结点，
    如果index等于链表长度，则将结点添加到链表末尾。
    如果index大于链表长度，则不会插入结点
    如果index小于0，则在头部插入结点。
     */
    void addAtIndex(int index, int val) {
        if(index<=0)
            addAtHead(val);
        else if(index==size)
            addAtTail(val);
        else if(index<size){
            node *cur=head;
            while(index--)
                cur=cur->next;
            // node *nxt=cur->next;
            // node *tmp=new node(val);
            // cur->next=tmp;
            // tmp->next=nxt;
            node *tmp=new node(val);
            // cur指向第index个结点的前一个
            tmp->next=cur->next;
            cur->next=tmp;
            ++size;
        }
    }
    
    /** 索引有效，则删除链表的第index个结点*/
    void deleteAtIndex(int index) {
        if(index>=size||index<0)
            return ;
        node *cur=head;
        while(index--)
            cur=cur->next;
        node *tmp=cur->next;
        cur->next=tmp->next;
        //tmp指向最后一个结点时，注意更新尾节点，
        if(!tmp->next)
            tail=cur;// cur指向第index个的前一个结点
        delete(tmp);
        --size;
    }
private:
    struct node{
        int val;
        node *next;
        node():val(0),next(nullptr){}
        node(int v):val(v),next(nullptr){}
    };
    node *head=nullptr;
    node *tail=nullptr;
    int size=0;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *curA=headA;
        ListNode *curB=headB;
        int lenA=0;
        int lenB=0;
        //计算A长度
        while(curA){
            lenA++;
            curA=curA->next;
        }
        //计算B长度
        while(curB){
            lenB++;
            curB=curB->next;
        }
        curA=headA;
        curB=headB;
        // 让curA指向长的链表,lenA为其长度。
        if(lenB>lenA){
            swap(lenA,lenB);
            swap(curA,curB);
        }
        // 计算两个链表的长度差；
        int gap=lenA-lenB;
        // curA指向链表的一个结点，使两个链表的末尾对齐
        while(gap--){
            curA=curA->next;
        }
        // 同时遍历，相等则返回结点
        while(curA){
            if(curA==curB){
                return curA;
            }
            curA=curA->next;
            curB=curB->next;
        }
        //不等，返回空。
        return NULL;
    }
};

class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        // 定义一个虚拟头结点， 方便处理
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        // 初始化指针
        ListNode g = dummyHead;
        ListNode p = dummyHead.next;

        // 将指针移到相应的位置
        for(int step = 0; step < m - 1; step++) {
            g = g.next; p = p.next;
        }

        // 头插法插入节点
        for (int i = 0; i < n - m; i++) {
            ListNode removed = p.next;
            p.next = p.next.next;

            removed.next = g.next;
            g.next = removed;
        }

        return dummyHead.next;
    }
}