程序员代码面试指南 2.14：在链表中删除指定值的节点

1、思路

• 用两个指针pre和cur来标记前一个节点和当前节点，若当前节点值为要删除的指定值，则将pre的下一节点指向cur的下一节点，即跳过当前节点；

• 时间复杂度 ，空间复杂度 。

2、代码

list_node * remove_value(list_node * head, int num)
{
    if (head == nullptr) return head;

    auto pre = head, cur = head->next;  //双指针
    while (cur != nullptr)
    {
        if (cur->val == num)
        {
            pre->next = cur->next;      //跳过当前节点，这一步pre无需改变指向
        }
        else
        {
            pre = cur;                  //上一节点指向当前节点
        }

        cur = cur->next;                //当前节点指向其下一节点
    }

    return head;
}