1.从尾到头打印链表
输入一个链表的头结点，按照 从尾到头 的顺序返回节点的值。

返回的结果用数组存储。

数据范围
0≤ 链表长度 ≤1000。

样例
输入：[2, 3, 5]
返回：[5, 3, 2]

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> printListReversingly(ListNode* head) {
        vector<int> a;
        while(head!=NULL)
        {
            a.push_back(head->val);
            head=head->next;
        }
        reverse(a.begin(),a.end());
        return a;
    }
};

2.在O(1)时间删除链表结点,删除指定节点
给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。

假设链表一定存在，并且该节点一定不是尾节点。

数据范围
链表长度 [1,500]。

样例
输入：链表 1->4->6->8
删掉节点：第2个节点即6（头节点为第0个节点）

输出：新链表 1->4->8

/**
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* newNode=new ListNode(-1);
        newNode=node->next;
        node->val=newNode->val;
        node->next=newNode->next;

    }
};

3.反转链表
定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题：

请同时实现迭代版本和递归版本。
数据范围
链表长度 [0,30]。

样例
输入:1->2->3->4->5->NULL

输出:5->4->3->2->1->NULL

迭代法:
空间复杂度分析：遍历时只有3个额外变量，所以额外的空间复杂度是 O(1)。
时间复杂度分析：只遍历一次链表，时间复杂度是 O(n)。
代码

/**
 * 
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode*cur=head;
        ListNode*pre=NULL;
        while(cur)
        {
            ListNode*ne=cur->next;
            cur->next=pre;
            pre=cur;
            cur=ne;
        }
        return pre;

    }
};

递归法：
首先我们先考虑 reverseList 函数能做什么，它可以翻转一个链表，并返回新链表的头节点，也就是原链表的尾节点。
所以我们可以先递归处理 reverseList(head->next)，这样我们可以将以head->next为头节点的链表翻转，并得到原链表的尾节点tail，此时head->next是新链表的尾节点，我们令它的next指针指向head，并将head->next指向空即可将整个链表翻转，且新链表的头节点是tail。
空间复杂度分析：总共递归 n 层，系统栈的空间复杂度是 O(n)，所以总共需要额外 O(n)的空间。
时间复杂度分析：链表中每个节点只被遍历一次，所以时间复杂度是 O(n)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode*tail = reverseList(head->next);
        head->next->next=head;
        head->next=NULL;
        return tail;

    }
};

4.合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

数据范围
链表长度 [0,500]。

样例
输入：1->3->5 , 2->4->5

输出：1->2->3->4->5->5

时间复杂度
两个链表各遍历一次，所以时间复杂度为O(n)
代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode*dummy = new ListNode(0);
        ListNode*cur=dummy;

        while(l1!=NULL&l2!=NULL)
        {
            if(l1->val<l2->val)
            {
                cur->next=l1;
                l1=l1->next;
            }
            else
            {
                cur->next=l2;
                l2=l2->next;
            }
            cur=cur->next;
        }
        if(l1!=NULL)
        {
            cur->next=l1;
        }
        else
        {
            cur->next=l2;
        }
        return dummy->next;
    }
};

5.删除排序链表中的重复元素(I)
给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。
输入：head = [1,1,2]
输出：[1,2]
输入：head = [1,1,2,3,3]
输出：[1,2,3]

时间复杂度
循环了一次链表,时间复杂度为O(n)
代码：

/**
 * 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* deleteDuplicates(ListNode* head) {
       ListNode*duyy = head;
        while(duyy!=NULL)
        {
            if(duyy->next!=NULL&&duyy->val==duyy->next->val)
            {
                duyy->next=duyy->next->next;
            }
            else
            {
                duyy=duyy->next;
            }
        }
        return head;
    }
};

6.删除排序链表中的重复元素(II)
在一个排序的链表中，存在重复的节点，请删除该链表中重复的节点，重复的节点不保留。

数据范围
链表中节点 val 值取值范围 [0,100]。
链表长度 [0,100]。

样例1
输入：1->2->3->3->4->4->5

输出：1->2->5
样例2
输入：1->1->1->2->3

输出：2->3

算法
(线性扫描)
之前做的删除节点的题是有重复元素只保留１个下来，这道题的要求是一个都不保留。(有点狠兄弟)
那么就要求在cur指针还没扫到重复元素区间的第一个元素的时候，就知道它们是重复元素了。
那么针对于２，解决方法是新建一个指针go，go = cur->next。就像cur相当于是上帝视角，是大佬，go是小兵向前冲。一般第一步cur->next->val是一定等于go->val的，接下来是继续判断，如果有重复元素，小兵go会继续向前冲，最后碰到不同元素，跳出while循环。
逻辑是这样：如果cur的后面是有一段相同元素，cur是不会涉足这段元素的，go会遍历这一段的每一个元素。最后，cur是相同元素区间的前一个节点，go是相同元素区间的后一个节点。
接下来的if判断，if(cur->next->next == go)成立意味着cur和go之间没有重复元素，那么cur向前走一步。如果else成立，说明有重复元素，那么cur->next指向go，直接略过相同元素这一段，相当于删除了这一段。
时间复杂度
O(n)

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head) {
        ListNode*dummy = new ListNode(-1);
        dummy->next=head;
        ListNode*cur=dummy;
        while(cur->next)
        {
            ListNode*go=cur->next;
            while(go&&cur->next->val==go->val)go=go->next;
            if(cur->next->next==go)cur=cur->next;
            else cur->next=go;
        }

        return dummy->next;
    }

};

7.链表中倒数第k个节点
输入一个链表，输出该链表中倒数第 k 个结点。

注意：

k >= 1;
如果 k 大于链表长度，则返回 NULL;
数据范围
链表长度 [0,30]。

样例
输入：链表：1->2->3->4->5 ，k=2

输出：4

时间复杂度:
1.先将链表反转，循环链表一次
2.后有循环一次链表查找第k位
时间复杂度为O(n)

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        ListNode*pre=NULL;
        ListNode*cur=pListHead;

        while(cur)
        {
            ListNode*ne=cur->next;
            cur->next=pre;
            pre=cur;
            cur=ne;
        }
        int i=1;

        while(pre&&i<k)
        {
            pre=pre->next;
            i++;
        }
        return pre;
    }
};

8.两个链表的第一个公共结点
输入两个链表，找出它们的第一个公共结点。

当不存在公共节点时，返回空节点。

数据范围
链表长度 [1,2000]。

样例
给出两个链表如下所示：
A：
····· a1 → a2
····· · ······ ↘
····················· c1 → c2 → c3
··················· · ↗
······ b1 → b2 → b3
B：

输出第一个公共节点c1

时间复杂度
循环链表 o(n)

注意：
没有公共节点，也会同时走到对方的NULL而相等的
为什么我运行if(p -> next)会错呢？
因为要考虑二者没有相交的情况，这个时候返回要让两个指针都指向尾部的null，要是写成（p->next)会发现自始至终指针没有指向尾部的NULL
代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        ListNode* p=headA;
        ListNode* q=headB;

        while(p!=q)
        {
            if(p)
            {
                p=p->next;
            }
            else
            {
                p=headB;
            }
            if(q)
            {
                q=q->next;
            }
            else
            {
                q=headA;
            }
        }
        return q;
    }
};

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { // 求链表A的长度
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { // 求链表B的长度
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap--) {
            curA = curA->next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

9.设计链表
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3

提示：

所有val值都在 [1, 1000] 之内。
操作次数将在  [1, 1000] 之内。
请不要使用内置的 LinkedList 库。

代码

class MyLinkedList {
public:
    struct ListNode
    {
        int val;
        ListNode*next;
        ListNode(int val):val(val),next(NULL){}
    };
    // 初始化链表
    MyLinkedList() {
        _dummyHead = new ListNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点
        _size = 0;
    }
    // index=0;是头节点(第一个节点)
    int get(int index) {
        if(index>_size-1||index<0)
        {
            return -1;
        }
        ListNode*p = _dummyHead->next;
        while(index--)
        {
            p=p->next;
        }
        return p->val;
    }

    void addAtHead(int val) {
        ListNode*node = new ListNode(val);
        node->next=_dummyHead->next;
        _dummyHead->next=node;
        _size++;
    }

    void addAtTail(int val) {
        ListNode*node= new ListNode(val);
        ListNode*cur=_dummyHead;
        while(cur->next)
        {
            cur=cur->next;
        }
        cur->next=node;
        _size++;
    }

    void addAtIndex(int index, int val) {
        ListNode*node=new ListNode(val);
        if(index>_size)return;
        ListNode*cur=_dummyHead;
        while(index--)
        {
             cur=cur->next;
        }
        node->next=cur->next;
        cur->next=node;
        _size++;
    }

    void deleteAtIndex(int index) {
        if(index>=0&&index<_size)
        {
            ListNode*cur=_dummyHead;
            while(index--)
            {
                cur=cur->next;
            }
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;//若只单纯留这一句，这多余的节点还在内存中没删除，消耗多余内存
            delete tmp;                 
            _size--;
        }
    }
      // 打印链表
    void printLinkedList() {
        ListNode* cur = _dummyHead;
        while (cur->next != nullptr) {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << endl;
    }
    private:
    int _size;
    ListNode* _dummyHead;
};  

/**
 * 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);
 */