常用操作

class MyLinkedList
{
public:
    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) {}
    };
    ListNode* head;
    int cnt;
    MyLinkedList()
    {
        cnt = 0;
        head = nullptr;
    }
    int get(int index)
    {
        if(index<0 || index>=cnt) return -1;
        ListNode *p = head;
        while(p)
        {
            if(index-- == 0) return p->val;
            p = p->next;
        }
    }
    void addAtHead(int val)
    {
        ListNode* p = new ListNode(val);
        p->next = head;
        head = p;
        cnt++;
    }
    void addAtTail(int val)
    {
        cnt++;
        if(!head)
        {
            head = new ListNode(val);
            return ;
        }
        ListNode* p = head;
        while(p->next)
        {
            p = p->next;
        }
        p->next = new ListNode(val);
        return ;
    }
    void addAtIndex(int index, int val)
    {
        if(index>cnt) return;
        if(index<=0)
        {
            addAtHead(val);
            return ;
        }
        if(index == cnt)
        {
            addAtTail(val);
            return ;
        }
        ListNode* p = head;
        cnt++;
        while(p->next)
        {
            if(--index == 0)
            {
                p->next = new ListNode(val,p->next);
                return ;
            }
            p = p->next;
        }
        return ;
    }
    void deleteAtIndex(int index)
    {
        if(index<0 || index>=cnt) return ;
        cnt--;
        if(index == 0)
        {
            head = head->next;
            return ;
        }
        ListNode* p = head;
        while(p->next)
        {
            if(--index == 0)
            {
                p->next = p->next->next;
                return ;
            }
            p = p->next;
        }
    }
    void pfList()
    {
        cout<<"cnt:"<<cnt<<endl;
        ListNode* p = head;
        while(p)
        {
            cout<<p->val<<' ';
            p = p->next;
        }
        cout<<endl;
        return ;
    }
};

翻转链表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* p = head;
        ListNode* post;
        ListNode* pre = nullptr;
        while(p) {
            post = p->next;
            p->next = pre;
            pre = p;
            p = post;
        }
        head = pre;
        return head;
    }
};

删除倒数第n个节点（双指针法+哑巴节点）

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

链表相交

注意相交的节点之后都是同一节点了，也就是后面的都合并了
一种做法是统计长度，然后从短的开始同时遍历，还有一种比较巧妙的解法是a+c+b+c=b+c+a+c：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* h1 = headA;
        ListNode* h2 = headB;
        while(h1 != h2){
            h1 = (h1 == nullptr ? headB : h1->next); 
            h2 = (h2 == nullptr ? headA : h2->next); 
        }
        return h1; 
    }
};

环形链表

可以使用快慢指针法， 分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。因为如果有环的话，相当于fast一个节点一个节点地追slow。
如何找到环的入口点？fast和slow相遇后的点设为index1，链表起始点设为index2，index1和2继续往后遍历必相遇，这时的相遇点就是环的入口。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while(index1!=index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return nullptr;
    }
};