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

2019年8月7日09:45:06 发表评论 46 views

链表基础

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

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

链表增删改查

要完成链表节点的查找、插入、删除与修改,需要特别留意前后指针的修改、空指针的处理。总得来说链表增删改查分三步:1/定义结束条件(一般为到达链表尾) 2/遍历链表 3/遍历过程中完成增删改查。

一些情况下会用哑节点(dummy node)来更方便对链表增删改查,这有时可以减少代码量。比如 LeetCode题目 203. Remove Linked List Elements:

    // 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则化解了这个问题。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: