删除满足某条件的节点

直接遍历比较麻烦，因为头结点和其他节点删除逻辑不同。简单方法：递归、虚拟头结点。

直接遍历代码

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

ListNode* removeElements(ListNode* head, int val) {
    ListNode* pre = head;
    ListNode* cur = head;
    ListNode* new_head = head;
    while (cur) {
        if (cur->val == val) {
            if (cur == new_head) {
                new_head = cur->next;
            } else
                pre->next = cur->next;
            ListNode* tem = cur;
            cur = cur->next;
            delete tem;
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
    return new_head;
}

递归

时间复杂度：O(n)，空间复杂度：O(n)。

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

虚拟头结点

在头结点前添加虚拟的头结点，统一头结点和其他节点的删除逻辑。时间复杂度：O(n)，空间复杂度：O(1)。可能涉及头结点的增删的情况，都可以使用虚拟头结点简化逻辑。

ListNode* removeElements(ListNode* head, int val) 
{
    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode* temp = dummyHead;
    while (temp->next) {
        if (temp->next->val == val) {
            temp->next = temp->next->next;
        } else {
            temp = temp->next;
        }
    }
    return dummyHead->next;
}

快慢指针：处理环形链表

快慢指针可用于检测链表中的环，并求出入环的第一个节点。原理：快指针每次移动两步，而慢指针每次只移动一步，当链表中存在环时，快指针与慢指针必定相遇。

设第一次相遇，快指针走了2k步，慢指针走了k步，环外长度a, 环长b
快指针多走了n圈(nb) --> k = nb , 慢指针走了nb步。

若慢指针再走a步，则一共走了a+nb步，刚好到达环入口

所以在慢指针和快指针相遇时，再使用一个指针ptr，初始它指向链表头部。随后，它和慢指针每次往后走一步，最后它们会在环入口相遇。

142. 环形链表 II - 力扣（LeetCode），题解代码写得很清楚。

此处，提供另一种解题思路：基于链表从头结点到尾结点依次使用new创建的假设，和堆地址从低到高生长的背景知识，令pre指针为前一节点，cur指针为当前节点。cur-pre>0，说明cur指向的节点在pre后面创建；cur-pre<=0，说明从链表尾部再次入环，且cur为入环的第一个节点。

ListNode* detectCycle(ListNode* head)
{
    // suppose that all nodes are created in sequence
    // 堆地址是从低到高生长
    ListNode* pre = head;
    if (!head || !head->next)
        return nullptr;
    ListNode* cur = head->next;
    while (cur) {
        if (cur - pre <= 0)
            return cur;
        pre = cur;
        cur = cur->next;
    }
    return nullptr;
}