知识点：

缺点：

无法高效获取长度
无法根据偏移快速访问元素
反转链表
方法一就是双指针来进行反转，注意要额外申请一个指针指向r指针，要不转完后面的内容就没了

c++

ListNode* reverseList(ListNode* head) {
       ListNode* l = NULL;
       ListNode* r = head;
       while(r != NULL){
           ListNode* cur = r->next;
           r->next = l;
           l = r; 
           r = cur;
       }
   return l;
   }

方法二递归
递归的设计要从两个方面入手，一个是返回什么，一个是得到上次的返回值当前层应该做怎么
这道题是应该返回链表的头结点，也就是原表的尾结点，做什么就是翻转了
翻转可以通过两步完成，假设当前操作的是phead，则通过

c++

1	head->next->next = head;

即可将p后面的节点指向p，然后我们要删除当前p指向后面的next指针

c++

1	head->next = NULL;

注意函数的返回值是p而不是next，我开始犯了这个错误，首先要明确最终返回的信息，我们不需要下个节点的信息（上面两步只用到了head），我们需要的p指向原来的尾结点并不断返回这个，在每层的函数完成翻转
下图就是回溯的过程，p始终指向尾结点

c++

ListNode* reverseList(ListNode* head) {
       if (head == NULL || head->next == NULL) {
           return head;
       }
       ListNode* p = reverseList(head->next);
       head->next->next = head;
       head->next = NULL;
       return p;
   }

环形链表
方法一：哈希表存储
遍历每个节点存起来，如果再次遍历已存节点就是环了·

c++

class Solution {
public:
    bool hasCycle(ListNode *head) {
        map<ListNode *,int>visit;
        while(head != NULL){
            if(visit[head] == 1)
                return true;
            visit[head] = 1;
            head = head -> next;
        }
        return false;
    }
};

方法二：快慢指针

c++

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head, *fast = head;
        while(fast && fast->next)                   //注意判断条件
        {
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)    return true;
        }
        return false;
    }
};

如果存在环，如何判断环的长度呢？方法是，快慢指针相遇后继续移动，直到第二次相遇。两次相遇间的移动次数即为环的长度。

移除链表元素
一道简单题卡了很久…太长时间不做链表果然忘记太多，下面总结一下几点错误

leetcode的链表都没有头节点，head指针直接指向第一个元素，所以如果想要删除第一个的元素的话需要自己建立一个头节点
开始代码写得是return head，如果第一个元素被删除了，那么head后面的指向就断掉了
最开始循环里是这么写的

c++

 if(p->next->val==val){
    p->next=p->next->next;
    p=p->next;
}

这样的话删除后就会跳过一个元素了。
下面代码，
常规

c++

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head==NULL)return NULL;
         ListNode*q = new ListNode(-1);
         q->next = head;
        ListNode*p = q;
        while(p->next!=NULL){
            if(p->next->val==val)
                p->next=p->next->next;
            else
                p=p->next;
        }
        return q->next;
    }
};

递归

c++

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if (!head)
            return head;
        head->next = removeElements(head->next, val);
        return head->val == val ? head->next : head;
    }
};

判断回文链表
最简单的方法就是用额外的空间把链表存到数组里再来判断，这里讲一下空间复杂度 $O(1)$ 的方法
我们需要先遍历到链表尾再和头结点对比，很容易想到递归，还是需要两个指针
递归的写法就是

先判断之前有没有不相等的点，这个用上层递归的返回值就可以了直接return false。
当前节点不相等return false
剩下就是相等了return true

c++

class Solution {
public:
    ListNode *first;
    bool recursive(ListNode* head){
        if(head != NULL){
            if(!recursive(head -> next))
                return false;
            if(head -> val != first -> val){
                return false;
            }
             first = first -> next;
        }
        return true;
    }
    bool isPalindrome(ListNode* head) {
        first = head;
        return recursive(head);
    }
};

反转链表
一次反转需要用到三个指针(l,r,p),l和r是指向当前要反转的两个节点，而p是保存r的下个节点，因为修改r->next = l, 下个节点的信息会丢失
注意原链表最后是指向NULL，所以反转的过程开头l也要指向NULL

c++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* l = NULL;
        ListNode* r = head;
        while(r){
            ListNode* p = r->next;
            r->next = l;
            l = r;
            r = p;
        }
        return l;
    }
};

递归：注意每层的返回都是原来的尾结点，每一层不需要上一层的信息就可以完成反转

c++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* p = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return p;
    }
};