算法与数据结构基础-链表（Linked List）增删改查

链表基础

与数组相比，链表在物理存储上是不连续的，不支持O(1)存储时间按索引。取出;但链表也有其优点，灵活的内存管理，允许在链表的任意位置插入和删除节点。单向链表的结构一般如下：

//Definition for singly-linked list.
    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };

链表的添加、删除、修改

要完成链表节点的查找、插入、删除、修改，需要特别注意修改前指针和后指针以及处理空指针。一般来说，链表的添加、删除、修改、检查分为三个步骤： 1/ 定义一个结束条件（一般是到达链表末尾） 2/ 遍历链表 3/ 完成添加、删除、在遍历过程中进行修改和检查。

在某些情况下使用虚拟节点可以更轻松地添加、删除、修改和检查链表，这有时可以减少代码量。比如LeetCode第203题，删除链表的元素：

    // 203. Remove Linked List Elements
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy=new ListNode(0);
        dummy->next=head;
        ListNode* cur=dummy;
        while(cur->next!=NULL){
            if(cur->next->val==val) cur->next=cur->next->next;
            else cur=cur->next;
        }
        return dummy->next;
    }

如果不使用上面的虚拟节点，如果要删除的节点是头节点，则需要特殊考虑和处理。使用虚拟节点可以解决这个问题。