算法与数据结构基础 – 链表(Linked List)增删改查

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

链表增删改查文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15104.html

要完成链表节点的查找、插入、删除与修改，需要特别留意前后指针的修改、空指针的处理。总得来说链表增删改查分三步：1/定义结束条件(一般为到达链表尾) 2/遍历链表 3/遍历过程中完成增删改查。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15104.html

一些情况下会用哑节点(dummy node)来更方便对链表增删改查，这有时可以减少代码量。比如 LeetCode题目 203. Remove Linked List Elements：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15104.html

    // 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;
    }

以上如果不使用dummy node，如果head是要被删除的节点，则需要特殊判断和处理，使用dummy node则化解了这个问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/15104.html